Merge Two Sorted Lists

Short Summary

Given two sorted linked list head nodes, merge the two into one sorted list. Use the existing nodes.

Example Diagram


I/O Example

// input1 := []int{1, 2, 4}
// input2 := []int{1, 3, 4}

// output := myFunction(input1, input2)

// output = []int{1, 1, 2, 3, 4, 4}

Explanation and Walk-through

We are given two sorted linked list head nodes. We want a single linked list containing all the nodes from the two input lists, and we would like to maintain the sorted order. This algorithm is similar to the merge operation in the merge sort. We will walk through both lists and exploit their state of being already sorted. At each step, we will pick the node with the smaller value and add it to our result linked list. Once we are done with one the lists, we keep adding the rest of the unfinished list. We must return the head node of the resulting list, so be aware how we keep the reference to the head node of the resulting list in a separate variable.

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
// start with heads of both lists
// compare them
// add the smaller one to the new list (this is the returned head)
// continue until one list is empty
// add the non-empty list members at the end of the list

if list1 == nil {
return list2
}
if list2 == nil {
return list1
}

var res *ListNode

node1 := list1
node2 := list2

if node1.Val < node2.Val {
res = node1
node1 = node1.Next
} else {
res = node2
node2 = node2.Next
}

cur := res

for node1 != nil && node2 != nil {
if node1.Val < node2.Val {
cur.Next = node1
node1 = node1.Next
} else {
cur.Next = node2
node2 = node2.Next
}
cur = cur.Next

}

for node1 != nil {
cur.Next = node1
node1 = node1.Next
cur = cur.Next
}

for node2 != nil {
cur.Next = node2
node2 = node2.Next
cur = cur.Next
}

return res
}

For the full code, feel free to reach out.

You can try it yourself on leetcode


Please comment or dm me if you have other questions or remarks.

Until next time,

Stay all in!

Reha S.

Oct 14 2022