How do you merge two sorted linked lists?

Create a dummy node as the start of the merged list and a tail pointer. Compare the heads of both lists. Attach the smaller node to tail's next, advance that list's head, and advance tail. Repeat until one list is exhausted, then attach the remaining list to tail. Return dummy's next as the merged head. This runs in O of n plus m time where n and m are the list lengths. The dummy node avoids special-casing the first element. This merge operation is the core building block for merge sort on linked lists, which achieves O of n log n sorting in O of one extra space.