# dmh2000.xyz

## 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

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}`

#### 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) 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}`