HomeLeetcode82. Remove Duplicates from Sorted List II - Leetcode Solutions
Leetcode

82. Remove Duplicates from Sorted List II – Leetcode Solutions

Declan Clarke

Description:

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

Examples:

Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:
Input: head = [1,1,1,2,3]
Output: [2,3]

Solution in Python:

Python
# 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:
        # Create a dummy node which helps in handling edge cases such as when the head itself needs to be deleted
        dummy = ListNode(0)
        dummy.next = head
        
        # Initialize pointers for the current node and the previous node
        prev = dummy
        current = head
        
        while current:
            # Flag to check if we have found any duplicates
            has_duplicate = False
            
            # Move the current pointer to the end of the current duplicate sequence
            while current.next and current.val == current.next.val:
                has_duplicate = True
                current = current.next
            
            if has_duplicate:
                # Skip all duplicates
                prev.next = current.next
            else:
                # Move the prev pointer to the current node if no duplicate was found
                prev = prev.next
            
            # Move the current pointer to the next node
            current = current.next
        
        # Return the modified list, starting from the next node of the dummy (which is the new head)
        return dummy.next

Explanation:

  1. ListNode Class:
    • A simple class to define the structure of a singly-linked list node with a value (val) and a pointer to the next node (next).
  2. Dummy Node:
    • We create a dummy node to simplify edge case handling, particularly when the head of the list itself needs to be removed. The dummy node’s next pointer points to the head of the list.
  3. Pointers:
    • prev: A pointer to the last node in the list that is guaranteed not to be part of any duplicates.
    • current: A pointer to the node currently being checked for duplicates.
  4. Traversal and Duplicate Detection:
    • We traverse the list with the current pointer.
    • If we encounter consecutive nodes with the same value, we move current to the last node in that sequence and set a flag (has_duplicate) to indicate that we have found duplicates.
  5. Skipping Duplicates:
    • If duplicates were found (has_duplicate is True), we skip over all duplicates by linking prev.next to current.next.
    • If no duplicates were found, we simply move the prev pointer to the current node.
  6. Update Current Pointer:
    • Move current to the next node to continue the traversal.
  7. Return Result:
    • Return dummy.next, which points to the head of the modified list without duplicates.

This method ensures that all nodes with duplicate values are removed from the list, leaving only distinct values, and it runs in O(n) time complexity where n is the number of nodes in the linked list.

Solution in Javascript:

JavaScript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // Create a dummy node to handle edge cases easily
    let dummy = new ListNode(0);
    dummy.next = head;
    
    // Initialize pointers for previous node and current node
    let prev = dummy;
    let current = head;
    
    while (current) {
        // Flag to check if there are duplicates
        let hasDuplicate = false;
        
        // Move the current pointer to the end of the duplicate sequence
        while (current.next && current.val === current.next.val) {
            hasDuplicate = true;
            current = current.next;
        }
        
        if (hasDuplicate) {
            // Skip all duplicates
            prev.next = current.next;
        } else {
            // Move the prev pointer to current if no duplicates were found
            prev = prev.next;
        }
        
        // Move the current pointer to the next node
        current = current.next;
    }
    
    // Return the modified list, starting from the next node of the dummy (new head)
    return dummy.next;
};

Solution in Java:

Java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // Create a dummy node to handle edge cases easily
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // Initialize pointers for previous node and current node
        ListNode prev = dummy;
        ListNode current = head;
        
        while (current != null) {
            // Flag to check if there are duplicates
            boolean hasDuplicate = false;
            
            // Move the current pointer to the end of the duplicate sequence
            while (current.next != null && current.val == current.next.val) {
                hasDuplicate = true;
                current = current.next;
            }
            
            if (hasDuplicate) {
                // Skip all duplicates
                prev.next = current.next;
            } else {
                // Move the prev pointer to current if no duplicates were found
                prev = prev.next;
            }
            
            // Move the current pointer to the next node
            current = current.next;
        }
        
        // Return the modified list, starting from the next node of the dummy (new head)
        return dummy.next;
    }
}

Solution in C#:

C#
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        // Create a dummy node to handle edge cases easily
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // Initialize pointers for previous node and current node
        ListNode prev = dummy;
        ListNode current = head;
        
        while (current != null) {
            // Flag to check if there are duplicates
            bool hasDuplicate = false;
            
            // Move the current pointer to the end of the duplicate sequence
            while (current.next != null && current.val == current.next.val) {
                hasDuplicate = true;
                current = current.next;
            }
            
            if (hasDuplicate) {
                // Skip all duplicates
                prev.next = current.next;
            } else {
                // Move the prev pointer to current if no duplicates were found
                prev = prev.next;
            }
            
            // Move the current pointer to the next node
            current = current.next;
        }
        
        // Return the modified list, starting from the next node of the dummy (new head)
        return dummy.next;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com