DSA Tracker

Visualize

Merge k Sorted Lists

Merging two sorted lists always produces another sorted list, so that result can be fed straight back into the same merge step as if it were just another input list — there's no need for a different algorithm once k grows past two. Fold the lists together one at a time: merge list1+list2, merge that sorted result with list3, and so on, each step reusing the same two-pointer comparison as merging two lists. Reach for it when combining more than two sorted sequences.

Details

Animated on: Pairwise merge of 3 sorted lists: [1,4,5] + [1,3,4] → [1,1,3,4,5], then merged with [2,6] → [1,1,2,3,4,5,6]

Problem:Merge k Sorted ListsHard

Pattern:Linked List Manipulation

Linked List

step 1 / 15

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

3 sorted lists: list1=[1,4,5] at idx0-2, list2=[1,3,4] at idx3-5, list3=[2,6] at idx6-7. Pass 1: mergeTwoLists(list1, list2).

  • 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
11FUNCTION mergeKLists(lists):
12  head = lists[0]
13  FOR i from 1 up to the length of lists:
14    head = mergeTwoLists(head, lists[i])
15  END FOR
16  RETURN head
17END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. 3 sorted lists: list1=[1,4,5] at idx0-2, list2=[1,3,4] at idx3-5, list3=[2,6] at idx6-7. Pass 1: mergeTwoLists(list1, list2).
  2. Compare l1[0]=1 vs l2[3]=1. Not less → else: append l2's node. l2 advances to idx4(3).
  3. Compare l1[0]=1 vs l2[4]=3. 1<3 → if: append l1's node. l1 advances to idx1(4).
  4. Compare l1[1]=4 vs l2[4]=3. 4<3 is false → else: append l2's node. l2 advances to idx5(4).
  5. Compare l1[1]=4 vs l2[5]=4. Not less → else: append l2's node. l2 exhausted (past idx5).
  6. l2 is null — exit loop. tail.next = l1 attaches the remaining l1 tail [4,5] (idx1, idx2) directly. Pass 1 result: [1,1,3,4,5].
  7. Pass 2: mergeTwoLists(pass-1 result, list3). merged=[1,1,3,4,5] at idx0-4, list3=[2,6] at idx5-6.
  8. Compare merged[0]=1 vs list3[5]=2. 1<2 → if: append merged's node. merged advances to idx1(1).
  9. Compare merged[1]=1 vs list3[5]=2. 1<2 → if: append merged's node. merged advances to idx2(3).
  10. Compare merged[2]=3 vs list3[5]=2. 3<2 is false → else: append list3's node. list3 advances to idx6(6).
  11. Compare merged[2]=3 vs list3[6]=6. 3<6 → if: append merged's node. merged advances to idx3(4).
  12. Compare merged[3]=4 vs list3[6]=6. 4<6 → if: append merged's node. merged advances to idx4(5).
  13. Compare merged[4]=5 vs list3[6]=6. 5<6 → if: append merged's node. merged exhausted (past idx4).
  14. merged is null — exit loop. tail.next = list3 attaches the remaining node [6] (idx6) directly.
  15. Return [1,1,2,3,4,5,6] — 3 lists merged across 2 pairwise passes.

Now solve it yourself

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

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