Skip to content

dmh2000.xyz

Remove Duplicates From Sorted List I and II (in Go)

2 min read

A couple of solutions for LeetCode 'Remove Duplicates from Sorted List I and II'


Remove Duplicates from Sorted List I

Problem : "Given a sorted linked list, delete all duplicates such that each element appears only once."

This one is relatively easy if you understand single linked lists. The LeetCode problem page gives you solutions. I'll show mine here but its nothing special. Just keep a previous pointer and a current pointer and skip over any node where value of previous == value of current

1func deleteDuplicates(head *ListNode) *ListNode {
2 var prev *ListNode
3 var node *ListNode
4 prev = head
5 node = prev.Next
6 for node != nil {
7 if node.Val == prev.Val {
8 // delete node
9 prev.Next = node.Next
10 } else {
11 prev = node
12 }
13 node = node.Next
14 }
15 return head
16}

Remove Duplicates from Sorted List II

Problem : "Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list." This one is rated 'medium'.

There are plenty of solutions on the web for this one as well, however most of them are 'golfing', which if you don't already know means solving in the minimum lines of code. That's a legit approach especially for interviews. For production code I prefer solutions that are easier to understand, possibly at the expense of additional O(?) complexity As long as the complexity is acceptable and it isn't (ON^2) or worse. Before you downvote me for that, keep in mind that there are algorithms for Mininum Spanning Tree that are better than Prim's or Kruskal's, with O(inverse-Ackermann) time.

In the usual solutions for this problem, there are some tricky compound logical expressions and sort-of complicated link dereferencing. In their favor, they are O(N) time and O(1) space (besides the linked list itself). My solution is O(N) time but O(N) space. But I contend its a lot easier to understand.

In my solution, rather than trying to figure out the complicated linking and if'ing, I do this: Go through the list once and just record the duplicates in a set. Then on a second pass check each node to see if its in the set, and if so, skip over it. Otherwise just move to next node. This also has the advantage that it doesn't require sorted input.

In the LeetCode environment this ran just as fast as the conventional solutions, at least to resolution of the LeetCode timing. I find that when using Go, and a fast solution, you can get 0ms or 4ms depending on when you submit.

If I produced this in an interview I and got pushback I would argue 'its easier to understand'. That might not fly unless I was able to show the O(1) space version as well. But at least I would have made my point on the way out the door.

1// O(N) time, O(N) memory
2func deleteDuplicates2(head *ListNode) *ListNode {
3 var m map[int]bool
4 var node *ListNode
5 var prev *ListNode
6
7 if head == nil {
8 return nil
9 }
10
11 // ============================================
12 // pass one find duplicates and map them
13 // ============================================
14 m = make(map[int]bool)
15 prev = head
16 node = prev.Next
17 for node != nil {
18 if node.Val == prev.Val {
19 // record the duplicate
20 m[node.Val] = true
21 }
22 prev = node
23 node = node.Next
24 }
25
26 // ============================================
27 // pass 2 remove nodes where Val is in the map
28 // ============================================
29 // dup in head is a special case, skip over dups
30 for head != nil {
31 _, inmap := m[head.Val]
32 if inmap {
33 head = head.Next
34 } else {
35 break
36 }
37 }
38
39 // might be empty
40 if head == nil {
41 return nil
42 }
43
44 // head is not a dup, so continue
45 prev = head
46 node = prev.Next
47 for node != nil {
48 _, inmap := m[node.Val]
49 if inmap {
50 // skip over this node
51 node = node.Next
52 prev.Next = node
53 } else {
54 // just advance to next node
55 prev = node
56 node = node.Next
57 }
58 }
59 return head
60}

Here's my Go test fixture if anyone cares (I doubt it). I have some utilities for working with LeetCode lists.

1func TestRemSort2(T *testing.T) {
2 var list *singleLinkedList
3 var head *ListNode
4
5 // I have a utility that builds a list from an array spec
6 // for use with LeetCode lists
7 list = buildList([]int{1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5})
8 head = list.head
9 head = deleteDuplicates2(head)
10 fmt.Print("should be [1] : ")
11 printList(head)
12 // i checked by printing and check
13
14 list = buildList([]int{1, 2, 3, 3, 4, 4, 5})
15 head = list.head
16 head = deleteDuplicates2(head)
17 fmt.Print("should be [1,2,5] :")
18 printList(head)
19
20 list = buildList([]int{1, 1, 2, 3, 3, 4, 4, 5})
21 head = list.head
22 head = deleteDuplicates2(head)
23 fmt.Print("should be [2,5] : ")
24 printList(head)
25
26 list = buildList([]int{})
27 head = list.head
28 head = deleteDuplicates2(head)
29 fmt.Print("should be nil : ")
30 printList(head)
31
32 list = buildList([]int{1})
33 head = list.head
34 head = deleteDuplicates2(head)
35 fmt.Print("should be [1] : ")
36 printList(head)
37
38 list = buildList([]int{1, 1})
39 head = list.head
40 head = deleteDuplicates2(head)
41 fmt.Print("should be nil : ")
42 printList(head)
43}