Remove duplicates from sorted list

Leetcode 82/83 remove duplicates from sorted list I&II [Python]

Table of Contents Show

Leetcode 82/83 remove duplicates from sorted list I&II [Python]
I. Keep one of the duplicates
LeetCode 83. Remove Duplicates from Sorted List
LeetCode – Remove Duplicates from Sorted List
Related posts:

Reference of ListNode class:

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

I. Keep one of the duplicates

input: 1->2->2->3->3->4

output: 1->2->3->4

class Solution:
def deleteDuplicates(self, head):
cur = head
while cur:
if cur.next and cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
return head

This one is pretty straight forward. We only need to check if the current node’s value is the same as its next node’s value. In order to do that, we keep a current node pointer. If the next node is not None and has the same value, we skip it by changing cur.next to cur.next.next . Otherwise, we keep updating the cur pointer to the next node.

In the end, we return head with all duplicates being skipped.

LeetCode 83. Remove Duplicates from Sorted List

by
Posted on April 4, 2021April 4, 2021

LeetCode – Remove Duplicates from Sorted List

Category: Algorithms January 17, 2013

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.

Thoughts

The key of this problem is using the right loop condition. And change what is necessary in each loop. You can use different iteration conditions like the following 2 solutions.

Solution 1

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null || head.next == null) return head; ListNode prev = head; ListNode p = head.next; while(p != null){ if(p.val == prev.val){ prev.next = p.next; p = p.next; //no change prev }else{ prev = p; p = p.next; } } return head; } }

Solution 2

public class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null || head.next == null) return head; ListNode p = head; while( p!= null && p.next != null){ if(p.val == p.next.val){ p.next = p.next.next; }else{ p = p.next; } } return head; } }