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:
- 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
).
- A simple class to define the structure of a singly-linked list node with a value (
- 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.
- 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
- 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.
- 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.
- We traverse the list with the
- Skipping Duplicates:
- If duplicates were found (
has_duplicate
isTrue
), we skip over all duplicates by linkingprev.next
tocurrent.next
. - If no duplicates were found, we simply move the
prev
pointer to the current node.
- If duplicates were found (
- Update Current Pointer:
- Move
current
to the next node to continue the traversal.
- Move
- Return Result:
- Return
dummy.next
, which points to the head of the modified list without duplicates.
- Return
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;
}
}