Merge Sorted Chains
Problem
Two singly linked lists are each already sorted in non-decreasing order. Splice them into one sorted list by relinking the existing nodes rather than creating new ones. Return the head of the merged list, which is empty when both inputs are empty.
Examples
Input: a = 1 -> 4 -> 6, b = 2 -> 3
Output: 1 -> 2 -> 3 -> 4 -> 6Input: a = empty, b = 7
Output: 7
Why: edge case, one side runs out before the loop startsInput: a = empty, b = empty
Output: empty
Why: edge case, there is nothing to mergeHints
0 / 3
At every moment only two candidates can come next: the current front of each chain. The rest of both chains is irrelevant until one of them is consumed.
Growing a list from the front is awkward, so keep a pointer to the last node of the result and always attach behind it. A throwaway starter node removes the special case for the very first attachment.
Repeatedly compare the two front nodes, detach the smaller one, and hang it off the tail of the result. When one chain empties, attach the entire remaining chain in a single step because it is already sorted.
Solution
The two chains are consumed front to front, always taking the smaller head and appending it to the tail of the result. A dummy starter node means the first append needs no special handling, and the real head is simply the node after it. When one chain runs dry, the other is already sorted, so the remainder is attached in one move instead of node by node. Time is O(n + m) and space is O(1), since only pointers change.
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def merge_sorted(a, b):
dummy = tail = Node(0) # starter node removes the empty-result case
while a and b:
if a.val <= b.val: tail.next, a = a, a.next
else: tail.next, b = b, b.next
tail = tail.next # the attached node is the new tail
tail.next = a or b # the leftover chain is already sorted
return dummy.next
print(dump(merge_sorted(build([1, 4, 6]), build([2, 3])))) # -> [1, 2, 3, 4, 6]
print(dump(merge_sorted(build([]), build([7])))) # -> [7]
print(dump(merge_sorted(build([]), build([])))) # -> []Stuck on the idea rather than the code? Singly Linked List Basics covers it.