Merge 2 sorted lists

Today, we look at another linked list task.

Create a function to merge 2 sorted linked lists. The resulting list should be a sorted list using the nodes of the 2 lists.

For this, we will use the generic linked list implementation from the previous post which can be found here

func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] { result := LinkedList[int]{} p1 := ll1.Head p2 := ll2.Head rp := &Node[int]{} // dummy node as result head result.Head = rp for p1 != nil && p2 != nil { if p1.Data >= p2.Data { rp.Next = p2 p2 = p2.Next } else { rp.Next = p1 p1 = p1.Next } rp = rp.Next } if p1 != nil { rp.Next = p1 } if p2 != nil { rp.Next = p2 } result.Head = result.Head.Next return result
}

The logic is pretty easy to follow. First, we setup pointers to the heads of the 2 lists and the resulting list. Since we don’t know the ‘head’ of the resulting list, we create a dummy node as a placeholder (we’ll fix that one later). We also create a current node, rp, for the result list.

Next, we iterate over the 2 lists. We have a current node for each list. At each step, we look at which of the 2 current nodes has the smaller value and put that node on the result list. Then move the current node of that list (the one that was smaller) to the next node in the list. We also need to move the current node of the result to the next place.

Our loop logic is simply to keep doing this until we reach the end of one of the lists. At this point, we know that there are no more elements to compare for one of the lists; they are already in the result list. So, we can then simply put the remaining nodes of the other list at the end of the result, since we know they are already sorted.

How would you do this different? Can we optimize this? Let me know in the comments.

Thanks!

The code for this post and all posts in this series can be found here