Merge two sorted linked lists into one sorted list.

How to think about it

What the interviewer is really watching here is whether you reuse the order you were handed. Both lists arrive already sorted, so anything that dumps them into an array and re-sorts is throwing away the one fact that makes the problem easy. They want to see you walk the two lists in lockstep and splice, not sort.

The pattern is the merge step of merge sort. You keep a pointer at the head of each list, compare the two front values, and pull the smaller one into your result. Then you advance only that list’s pointer and compare again. Because both lists are sorted, the smaller of the two heads is always the smallest element you haven’t placed yet — so a single left-to-right sweep produces a fully sorted output. The one wrinkle with linked lists is the very first node: you don’t yet have a result to attach to. The fix is a dummy sentinel — a throwaway node you build the answer behind, so tail.next = smaller works on every step, including the first. When one list runs dry, you don’t walk the other; you just point tail.next at whatever remains, since it’s already sorted.

A worked example

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def from_list(lst):
    dummy = Node(0)
    tail = dummy
    for v in lst:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next

def merge_sorted(a, b):
    dummy = Node(0)                 # sentinel: build the answer behind it
    tail = dummy
    while a and b:
        if a.val <= b.val:          # <= keeps it stable for equal values
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b              # one list is empty; attach the rest as-is
    return dummy.next               # skip the sentinel

print(to_list(merge_sorted(from_list([1, 3, 5]), from_list([2, 4, 6]))))
print(to_list(merge_sorted(from_list([1, 2, 3]), None)))   # one list empty
print(to_list(merge_sorted(None, None)))                    # both empty
print(to_list(merge_sorted(from_list([5]), from_list([1, 2, 3, 4]))))

[1, 2, 3, 4, 5, 6]
[1, 2, 3]
[]
[1, 2, 3, 4, 5]

The first line is the heart of it: two disjoint sorted lists interleave into one. The last line is the case that catches people — a single large value in list a against a longer list b. The loop attaches 1, 2, 3, 4 from b first, then the while exits when b empties, and tail.next = a or b hangs the lone 5 on the end. No node was copied; you only rewired next pointers, which is why the space cost is constant.