Merge Two Sorted Lists
Module 7 · Linked Lists
Problem
Given the heads of two sorted linked lists, merge them into one sorted list by splicing together the existing nodes (no new value copies), and return its head.
Examples
Example 1
Input
list1 = [1,2,4], list2 = [1,3,4]Output[1,1,2,3,4,4]Example 2
Input
list1 = [], list2 = []Output[]Example 3
Input
list1 = [], list2 = [0]Output[0]Constraints
0 ≤ each length ≤ 50 · both inputs sorted.
Attempt it first
This is the dummy node's signature problem — and the merge step you'll meet again inside merge sort (Module 14) and k-way merging (Module 19). The rewire-don't-copy discipline from the surgery lesson is the whole game. Sketch two short lists and stitch them on paper first.