LeetCode #83 Remove Duplicates from Sorted List

Posted on | Post modified | In , , , , , ,

Problem

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

Examples

1
2
3
4
5
Input: 1->1->2
Output: 1->2

Input: 1->1->2->3->3
Output: 1->2->3

Solution

Method: Two Pointers

Time Complexity: O(n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        
        current_ptr = head
        detect_ptr = head.next
        
        while current_ptr and detect_ptr:
            if current_ptr.val == detect_ptr.val:
                detect_ptr = detect_ptr.next
                continue
            else:
                current_ptr.next = detect_ptr
                current_ptr = detect_ptr
                detect_ptr = detect_ptr.next
        
        if current_ptr.next:
            current_ptr.next = None
            
        return head

Note

Don’t forget to check the boundary condition. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 1->2->3

Iteration 1:
    current_ptr.val = 1
    detect_ptr.val = 2

Iteration 2:
    current_ptr.val = 2
    detect_ptr.val = 3

Iteration 3:
    current_ptr.val = 3
    detect_ptr = None

What's now?
    current_ptr.val = 3
    current_ptr.next = None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input: 1->2->2

Iteration 1:
    current_ptr.val = 1
    detect_ptr.val = 2

Iteration 2:
    current_ptr.val = 2 (the first 2)
    detect_ptr.val = 2 (the second 2)

Iteration 3:
    current_ptr.val = 2 (the first 2)
    detect_ptr = None

What's now?
    current_ptr.val = 2
    current_ptr.next.val = 2
    => we need to set the current_ptr.next to None