Skip to content## Remove Duplicates From Sorted List I and II (in Go)

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

#### Remove Duplicates from Sorted List I

#### Remove Duplicates from Sorted List II

— 2 min read

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 *ListNode3 var node *ListNode4 prev = head5 node = prev.Next6 for node != nil {7 if node.Val == prev.Val {8 // delete node9 prev.Next = node.Next10 } else {11 prev = node12 }13 node = node.Next14 }15 return head16}`

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) memory2func deleteDuplicates2(head *ListNode) *ListNode {3 var m map[int]bool4 var node *ListNode5 var prev *ListNode67 if head == nil {8 return nil9 }1011 // ============================================12 // pass one find duplicates and map them13 // ============================================14 m = make(map[int]bool)15 prev = head16 node = prev.Next17 for node != nil {18 if node.Val == prev.Val {19 // record the duplicate20 m[node.Val] = true21 }22 prev = node23 node = node.Next24 }2526 // ============================================27 // pass 2 remove nodes where Val is in the map28 // ============================================29 // dup in head is a special case, skip over dups30 for head != nil {31 _, inmap := m[head.Val]32 if inmap {33 head = head.Next34 } else {35 break36 }37 }3839 // might be empty40 if head == nil {41 return nil42 }4344 // head is not a dup, so continue45 prev = head46 node = prev.Next47 for node != nil {48 _, inmap := m[node.Val]49 if inmap {50 // skip over this node51 node = node.Next52 prev.Next = node53 } else {54 // just advance to next node55 prev = node56 node = node.Next57 }58 }59 return head60}`

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 *singleLinkedList3 var head *ListNode45 // I have a utility that builds a list from an array spec6 // for use with LeetCode lists7 list = buildList([]int{1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5})8 head = list.head9 head = deleteDuplicates2(head)10 fmt.Print("should be [1] : ")11 printList(head)12 // i checked by printing and check1314 list = buildList([]int{1, 2, 3, 3, 4, 4, 5})15 head = list.head16 head = deleteDuplicates2(head)17 fmt.Print("should be [1,2,5] :")18 printList(head)1920 list = buildList([]int{1, 1, 2, 3, 3, 4, 4, 5})21 head = list.head22 head = deleteDuplicates2(head)23 fmt.Print("should be [2,5] : ")24 printList(head)2526 list = buildList([]int{})27 head = list.head28 head = deleteDuplicates2(head)29 fmt.Print("should be nil : ")30 printList(head)3132 list = buildList([]int{1})33 head = list.head34 head = deleteDuplicates2(head)35 fmt.Print("should be [1] : ")36 printList(head)3738 list = buildList([]int{1, 1})39 head = list.head40 head = deleteDuplicates2(head)41 fmt.Print("should be nil : ")42 printList(head)43}`