
Problem Statement
In this task, we are working with a sorted linked list. Each node in this linked list contains an integer value, and we are to process the list to eliminate all duplicates. By duplicates, we mean any number that occurs more than once consecutively in the list. The result will be a new linked list containing only those numbers that appear exactly once in the original list, with the order preserved. Importantly, the output list must also remain sorted.
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]
Constraints
- The number of nodes in the list is in the range
[0, 300]
. -100 <= Node.val <= 100
- The list is guaranteed to be sorted in ascending order.
Approach and Intuition
To solve this problem, one can think through it using a simple iterative approach:
- Traverse the linked list using a pointer, let's call it
current
. - Set up a dummy node which acts as a placeholder to build the new linked list without duplicates.
- Use a pointer attached to this dummy node to keep track of the end of your new list as you add eligible nodes to it.
- As you iterate through the list with
current
, check the next node to ensure you don't have duplicates; this can be done since the list is already sorted. - If
current
is a unique node (based on comparison with the nodes immediately before and after), append it to the list linked to the dummy node. If not, skip until a new value is found. - Make sure to handle head and tail of the list properly, as they don't have both previous and next nodes for comparison in all cases.
- Ultimately, the
next
pointer of your dummy node will be connected to the head of the new list you formed.
Edge cases to consider:
- If the list is empty (i.e., the
head
isnull
), returnnull
directly. - If the list has all duplicate numbers or all unique numbers, ensure your solution can handle these extremes.
- Consider lists with maximum constraints, i.e., 300 nodes, to make sure your solution works efficiently within these limits.
Considering the constraints given:
- The number of nodes will not be overwhelmingly large, so an efficient iteration is feasible.
- All list values fall within a reasonable integer range, ensuring numerical operations or comparisons aren't complex or error-prone.
- The provided list is always sorted, which greatly simplifies the problem as you can make decisions based on adjacent nodes only.
Solutions
- C++
- Java
- C
- JavaScript
- Python
class Solution {
public:
ListNode* removeDuplicates(ListNode* start) {
ListNode* fakeHead = new ListNode(0, start);
ListNode* previous = fakeHead;
while (start != NULL) {
if (start->next != NULL && start->val == start->next->val) {
while (start->next != NULL && start->val == start->next->val) {
start = start->next;
}
previous->next = start->next;
} else {
previous = previous->next;
}
start = start->next;
}
return fakeHead->next;
}
};
The solution provided is a C++ implementation that efficiently removes all duplicate nodes from a sorted linked list, where the list is ordered in non-decreasing order. This is accomplished by retaining only those nodes that do not have a duplicate entry. Here is a step-by-step breakdown of how the solution operates:
Create an auxiliary 'fakeHead' node. This node points to the start of the actual list, facilitating the handling of edge cases, such as when the initial nodes are duplicates.
Initialize a pointer 'previous' at 'fakeHead' to track the last node in the sequence of unique nodes.
Iterate through the list starting from the head. Use the pointer 'start' for traversal.
Check if the current node ('start') and its successor ('start->next') have the same value. If they do, continue moving 'start' forward until the end of the duplicates sequence is found.
Once the end of the duplicates sequence is reached, connect the 'previous' node to the node following the last duplicate ('start->next'), effectively skipping over all the duplicates.
If 'start' and 'start->next' are not duplicates, move the 'previous' pointer to 'previous->next' (which points to 'start').
Move 'start' to 'start->next' to check the next set of elements.
After the loop, return the next node to 'fakeHead', which is the start of the modified list free of duplicates.
This approach ensures a robust solution with a time complexity dominantly governed by the linear traversal of the list, thereby accomplishing the removal operation efficiently in-place.
class Solution {
public ListNode removeDuplicates(ListNode headNode) {
ListNode initialNode = new ListNode(0, headNode);
ListNode lastUnique = initialNode;
while (headNode != null) {
if (headNode.next != null && headNode.val == headNode.next.val) {
while (headNode.next != null && headNode.val == headNode.next.val) {
headNode = headNode.next;
}
lastUnique.next = headNode.next;
} else {
lastUnique = lastUnique.next;
}
headNode = headNode.next;
}
return initialNode.next;
}
}
The provided Java solution aims to remove all elements that appear more than once in a sorted linked list, ensuring that no duplicates remain. The approach involves maintaining pointers to traverse through the linked list and handle duplicates effectively. Here’s a breakdown of the operations performed in the code to understand the functionality better:
- Create a placeholder node (
initialNode
) pointing to the head of the list. This node helps in easily returning the modified list without handling edge cases where the head might be removed. - Use a pointer
lastUnique
to track the last node in the list that confirmedly has no duplicates. - Traverse the list using the
headNode
pointer. During each iteration, check for duplicates by comparing the node's value with its next node's value. - If a duplicate is detected (
headNode.val == headNode.next.val
), skip all consecutive nodes that have the same value. - Adjust the
lastUnique.next
to connect with the next node after the last duplicate. - If no duplicate is found, move the
lastUnique
pointer one step forward. - Continue the process until
headNode
traverses all nodes. - Return the next node of
initialNode
, which is the head of the modified list without duplicates.
Execute this block of code to modify a sorted linked list by removing all elements that are duplicated, leaving only distinct numbers that originally appeared in the list. Make sure to handle edge cases like an empty list or a list where all elements are the same.
struct ListNode* removeDuplicates(struct ListNode* start) {
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = start;
struct ListNode* previous = dummy;
while (start != NULL) {
if (start->next != NULL && start->val == start->next->val) {
while (start->next != NULL && start->val == start->next->val) {
start = start->next;
}
previous->next = start->next;
} else {
previous = previous->next;
}
start = start->next;
}
return dummy->next;
}
The provided C code defines a function to remove all elements from a sorted linked list that have duplicates. The function is named removeDuplicates
and it takes a pointer to the first node of a linked list as its parameter. The function's goal is to ensure that each value in the linked list appears exactly once, removing any duplicates entirely, not just their additional occurrences.
Here's a breakdown of the steps the function takes:
Create a dummy node, which will help in easily removing nodes at the beginning of the list if they are duplicates. This dummy node initially points to the start of the list.
Use two pointers:
previous
– Starts at the dummy node.start
– Used to traverse the list.
Iterate through the list with the
start
pointer. For each node:- Check if the current node and the next node have the same value. If so, there are duplicates, and you find the last node in this sequence of duplicates.
- Update
previous->next
to skip over all the detected duplicates. - If no duplicates are found, simply move the
previous
pointer to the next node.
Return the modified list, which starts after the dummy node.
This solution effectively handles the removal of duplicates by skipping over all nodes that have the same value consecutively in the list. After using this function, the returned linked list will have only unique elements remaining from the original list, each appearing exactly once.
var removeDuplicates = function (firstNode) {
let initial = new ListNode(0, firstNode);
let previous = initial;
while (firstNode !== null) {
if (firstNode.next !== null && firstNode.val === firstNode.next.val) {
while (firstNode.next !== null && firstNode.val === firstNode.next.val) {
firstNode = firstNode.next;
}
previous.next = firstNode.next;
} else {
previous = previous.next;
}
firstNode = firstNode.next;
}
return initial.next;
};
The provided solution effectively removes duplicates from a sorted linked list using JavaScript. Here's how it accomplishes this:
- Initialize a new list node (
initial
) with zero as a value andfirstNode
as its next node to simplify edge cases handling (head duplicates). - Use a pointer
previous
to keep track of the last node before the duplicate sequence starts. - Iterate over the list starting from the first node. The loop continues until there are no more nodes to examine (
firstNode
becomesnull
). - Check if the current node (
firstNode
) has a duplicate immediately next (firstNode.val === firstNode.next.val
). If duplicates are found:- Continue to traverse until the end of duplicates.
- Set the
previous.next
to point to the node right after the last duplicate, effectively skipping the entire sequence of duplicate values.
- If no duplicates are detected for the current node, simply move the
previous
pointer toprevious.next
. - After ending the duplication check loop, the pointer
firstNode
also moves to the next node. - Return
initial.next
, which points to the head of the modified list where all duplicates have been removed.
This approach ensures that all nodes with values that appear more than once in the sorted linked list are completely removed, leaving only distinct values.
class Solution:
def removeDuplicates(self, start: ListNode) -> ListNode:
# Create initial node
initial = ListNode(0, start)
# Previous node tracker
previous = initial
while start:
# Check for the start of duplicates
if start.next and start.val == start.next.val:
# Find the end of duplicates
while start.next and start.val == start.next.val:
start = start.next
# Connect to the next new value
previous.next = start.next
else:
# Move the previous pointer
previous = previous.next
# Proceed to next node
start = start.next
return initial.next
The provided Python solution works to remove duplicates from a sorted linked list where numbers that appear more than once are all removed completely. Here's a breakdown of how the code accomplishes this:
- Define a dummy or sentinel node,
initial
, and set itsnext
pointer to the head of the list,start
. This node helps easily manage nodes at the head of the list. - Use a
previous
point which initially points to this dummy node. This helps in easily connecting and managing the preceding nodes. - Iterate through the linked list using a while loop on
start
. - Inside the loop, check if the current node (
start
) and its next node (start.next
) have the same value, indicating the start of a sequence of duplicates.- If they do, skip all nodes in this sequence by continuing to move the
start
pointer as long as subsequent nodes have the same value. - Once the end of duplicates is reached, make the
previous.next
point tostart.next
, effectively skipping over all the duplicates.
- If they do, skip all nodes in this sequence by continuing to move the
- If the current node is not a duplicate, simply move the
previous
pointer to the current node (start
), thus keeping it linked to the non-duplicate sequence. - Continuously move
start
to the next node in the list. - Finally, return the new list starting from the node right after the dummy node (
initial.next
), which represents the head of the modified list.
This method efficiently handles the removal of all nodes in the list that have duplicate values and retains only those nodes that appear exactly once.
No comments yet.