Merge Two Sorted Lists

Easy

The problem

You get the heads of two linked lists, each sorted from smallest to biggest. Join them into one sorted linked list made from the existing nodes, and return its head.

Example 1
Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
All six values in sorted order.
Example 2
Input: list1 = [], list2 = [0]
Output: [0]
One list is empty, so the result is the other.
Example 3
Input: list1 = [], list2 = []
Output: []
Both are empty.

Limits

0 ≤ length of each list ≤ 50,000
-100 ≤ node value ≤ 100
Both lists are sorted in non-decreasing order

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A dummy head node means you never have to special-case the first element.

The idea

Compare the two heads, append the smaller to a tail pointer, advance that list; at the end attach whichever list remains.

Target: O(n + m) time, O(1) space

Go function shape

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode

Reference solution

Tested with go test. Try it yourself first, then compare.

// MergeTwoLists: splice two sorted lists into one.
// The dummy node removes the "which node is the head?" special case.
func MergeTwoLists(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val { // <= keeps the merge stable
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a // at most one list has leftovers: attach it whole
	} else {
		tail.Next = b
	}
	return dummy.Next
}

Read the lesson: Linked List · Fast & Slow Pointers