Sponsored
Sponsored
In this approach, we'll use two pointers: prev and current. The prev pointer will be the last node in the result list without duplicates, and current pointer will traverse the input list. We initialize a dummy node before the head to simplify the edge case management when duplicates are at the start of the list.
While traversing, if the current node has the same value as the next node, we keep moving forward to skip all nodes with this value. If prev.next points to the current node when a duplicate sequence starts, we simply remove the sequence by connecting prev to the node after the last duplicate.
Time Complexity: O(n), where n is the number of nodes in the list, because each node is visited at most twice.
Space Complexity: O(1), as no additional space is used aside from a few pointers.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode
The C solution defines a ListNode structure to represent each node in the linked list. A dummy node is initialized with dummy.next pointing to head. Two pointers, prev and current, are used to traverse and modify the linked list to remove duplicates. The while loop ensures that all duplicates are detected and skipped over, while prev is maintained to ensure only distinct numbers are retained in the list.
This approach utilizes recursion to elegantly process the list for duplicates. The concept centers on calling a helper function that, at each level, processes the current node list by recursively evaluating burdens of duplicates. The recursion simplifies decision-making by naturally moving through the list and sorting out duplicate removal due to stack calls automatically handling execution follow-through.
Each call checks for duplicate patterns and recursively bridges connections between unique nodes. This allows the call stack to effectively tackle the transformation demands of duplicate filtering through returning modified structures created per recursion.
Time Complexity: O(n), visiting each node once recursively.
Space Complexity: O(n), accounting for call stack space in recursion.
1class ListNode:
2 def __init__(self, val=
The Python recursive solution systematically checks each node and its successively linked node's equality. When duplicates are found, the head progress skips them altogether, recursively pursuing a clean node linkage post-duplicate skipping.