Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/82.html

82	Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers,
leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

@tag-linkedlist

Algorithm

In this problem, we need to remove all duplicates from a linked list. The linked list may have duplicates at the beginning, and hence, deleting nodes from the beginning can change the head pointer of the linked list. Therefore, we need to define a new node, link the original linked list to it, and then define two pointers: a predecessor pointer and a current pointer. Both pointers start from the new node, and the current pointer moves down the list.

  • If the current pointer encounters the same value as its predecessor, it moves forward until it finds a different value. Then, the next of the predecessor pointer is updated to point to the different element below.
  • If the first element traversed by the current pointer is not the same as its predecessor, we move the predecessor pointer down one position.

In the end, we need to return the head pointer of the linked list.

Code

Java

  • 
    public class Remove_Duplicates_from_Sorted_List_II {
    
    	public ListNode deleteDuplicates(ListNode head) {
    
    		if (head == null) {
    			return head;
    		}
    
    		ListNode dummy = new ListNode(0);
    		dummy.next = head;
    
    		ListNode prev = dummy;
    		ListNode current = head;
    
    		while (current != null) {
    
    			boolean dup = false;
    
    			// probe next to see if duplicate
    			while (current.next != null && current.val == current.next.val) {
    				current = current.next;
    				dup = true;
    			}
    
    			if (dup) { // prev staying the same
    				prev.next = current.next;
    				current = current.next;
    			} else {
    				prev = current;
    				current = current.next;
    			}
    		}
    
    		return dummy.next;
    	}
    
    }
    
  • // OJ: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            ListNode dummy, *tail = &dummy;
            while (head) {
                int val = head->val;
                if (head->next && head->next->val == val) {
                    while (head && head->val == val) head = head->next;
                } else {
                    tail->next = head;
                    tail = head;
                    head = head->next;
                }
            }
            tail->next = nullptr;
            return dummy.next;
        }
    };
    
  • # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            dummy = ListNode(-1, head)
            cur = dummy
            while cur.next and cur.next.next:
                if cur.next.val == cur.next.next.val:
                    val = cur.next.val
                    while cur.next and cur.next.val == val:
                        cur.next = cur.next.next
                else:
                    cur = cur.next
            return dummy.next
    
    ############
    
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
      def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        p = dummy
        while p.next:
          if p.next.next and p.next.val == p.next.next.val:
            z = p.next
            while z and z.next and z.val == z.next.val:
              z = z.next
            p.next = z.next
          else:
            p = p.next
        return dummy.next
    
    

All Problems

All Solutions