Merge Two Sorted Lists
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Merge two sorted linked lists into one sorted list by relinking the existing nodes.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which node must come first in the merged list?
- Hint 2Keep a tail marker and attach the smaller front node each time.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two sorted queues at two counters, each ordered by token number, must be combined into one line at a single counter. Two clerks look at the front person of each queue and wave through the one with the smaller token. Repeat. When one queue is empty, the rest of the other queue simply follows. A "tail marker" at the end of the new line is where the next person attaches.
- The obvious way
Collect all values, sort, rebuild: O((n+m) log(n+m)) and extra nodes.
- The key insight
Make a dummy node to start the new list so there is always a tail to attach to. Compare the two front nodes, attach the smaller one to the tail and step that list forward. When one list is exhausted, attach the whole remaining list in one move.
- The algorithm
- Make a dummy start node; the tail marker begins there.
- Compare the front nodes of both lists; attach the smaller one to the tail.
- Move that list forward and move the tail onto the attached node.
- When one list ends, attach the other list's remainder. Return dummy's next.
Watch it run
Examplefirst = 1 -> 2 -> 4, second = 1 -> 3 -> 4
Fronts are 1 and 1. Equal: take the first list's 1.
merged: 1
Where people slip
- Without a dummy node you must special-case the first node; the dummy removes that bug source.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# ListNode is provided
def merge_two_lists(first, second):
dummy = ListNode()
tail = dummy # where the next node will attach
while first and second:
if first.val <= second.val:
tail.next = first
first = first.next
else:
tail.next = second
second = second.next
tail = tail.next
tail.next = first or second # attach whatever is left
return dummy.nextNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.