DSA Tracker

Visualize

Merge Two Sorted Lists

Because both lists are already sorted, the smallest value not yet placed in the output has to be sitting at the front of one of the two lists — there's no need to look any deeper than the two current heads. So compare l1 and l2's current nodes, attach whichever is smaller to the output, and advance only that list's pointer; repeat until one list runs out, then splice on whatever's left of the other. Reach for it whenever combining two sorted sequences.

Details

Animated on: Merge two sorted lists [1,2,4] and [1,3,4] into one sorted output

Problem:Merge Two Sorted ListsEasy

Pattern:Linked List Manipulation

Linked List

step 1 / 8

1
[0]
2
[1]
4
[2]
1
[3]
3
[4]
4
[5]

Input: l1=[1,2,4] at idx0-2, l2=[1,3,4] at idx3-5. l1 at idx0(1), l2 at idx3(1).

  • l1=0· arr[0] = 1
  • l2=3· arr[3] = 1
Pseudocode
1FUNCTION mergeTwoLists(l1, l2):
2  make a dummy start node; tail = dummy
3  WHILE both l1 and l2 still have nodes:
4    IF l1's value < l2's value: attach l1's node after tail; move l1 forward
5    ELSE: attach l2's node after tail; move l2 forward
6    tail = the node after tail
7  END WHILE
8  attach whichever list still has nodes after tail
9  RETURN the node after dummy
10END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Input: l1=[1,2,4] at idx0-2, l2=[1,3,4] at idx3-5. l1 at idx0(1), l2 at idx3(1).
  2. Compare l1[0]=1 vs l2[3]=1. Not strictly less (1<1 is false) → else branch: append l2's node. l2 advances to idx4(3).
  3. Compare l1[0]=1 vs l2[4]=3. 1<3 → if branch: append l1's node. l1 advances to idx1(2).
  4. Compare l1[1]=2 vs l2[4]=3. 2<3 → if branch: append l1's node. l1 advances to idx2(4).
  5. Compare l1[2]=4 vs l2[4]=3. 4<3 is false → else branch: append l2's node. l2 advances to idx5(4).
  6. Compare l1[2]=4 vs l2[5]=4. Not strictly less → else branch: append l2's node. l2 exhausted (moves past idx5, becomes null).
  7. l2 is null, loop condition (l1 && l2) is now false — exit loop. Attach the remaining l1 tail directly: tail.next = l1 (just node 4 left).
  8. Return merged list [1,1,2,3,4,4] — every node examined exactly once across both lists.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Merge Two Sorted Lists in the editorAll Linked List problemsBack to roadmap