Delete duplicate-value nodes from a sorted Linked list| Linked List
TASK(easy)
You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty.
Example
head refers to the first node in the list.
1->2->2->3->3->3->3->NULL
Remove 1 of the 2 data values and return head pointing to the revised list.
Function Description
Complete the removeDuplicates function in the editor below.
removeDuplicates has the following parameter:
- SinglyLinkedListNode pointer head: a reference to the head of the list
Returns
- SinglyLinkedListNode pointer: a reference to the head of the revised list
Input Format
The first line contains an integer t, the number of test cases.
The format for each test case is as follows:
The first line contains an integer n, the number of elements in the linked list.
Each of the next n lines contains an integer, the data value for each of the elements of the linked list.
Constraints
1<=t<=10
1<=n<=1000
1<=list[i]<=1000
Sample Input
STDIN Function
----- --------
1 t = 1
5 n = 5
1 data values = 1, 2, 2, 3, 4
2
2
3
4
Sample Output
1 2 3 4
SOLUTION 1
def removeDuplicates(llist):
data_set = set()
previous_ptr = None
current_ptr = llist
#loop removing the duplicated data
while current_ptr:
if current_ptr.data in data_set:
#removing the duplicated data node
previous_ptr.next = current_ptr.next
del current_ptr
current_ptr = previous_ptr.next
else:
data_set.add(current_ptr.data)
previous_ptr = current_ptr
current_ptr = current_ptr.next
return llist
SOLUTION 2
def removeDuplicates(llist):
haystack = dict()
prev = None
cur = llist
while cur:
if cur.data in haystack:
prev.next = cur.next
else:
prev = cur
haystack[cur.data] = True
cur = cur.next
return llist
EXPLANATION STEPS
- Initialize
currentto the head. - While Loop: Traverse the list:
- If the current node’s data equals the next node’s data, remove the next node.
- If not, move
currenttocurrent.next.
- Finish: All duplicates are removed.
