Merge Two Sorted Lists

Short Summary

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

---

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