11.07Beginner / Intermediate5 topics18 min4 interactive animations

Linked list merging

Merging and combining lists: merge two sorted lists, merge k sorted lists with a heap, add two numbers stored as lists, find the intersection of two lists and remove duplicates from a sorted list.

Learning goals

Merge sorted lists by relinking nodes
Merge k lists with a priority queue
Add numbers digit by digit with a carry
Find a shared tail with two pointers

Prerequisites

Singly linked operations

11.07.1

Merge two sorted lists

Keep a dummy node and a tail; repeatedly attach the smaller of the two front nodes to the tail and advance that list. When one list runs out, attach the rest of the other in one step. No nodes are copied: only next pointers change. O(n + m) time, O(1) extra space. Using <= on ties keeps the merge stable.

Step through the default merge and the preset where one list runs out early.

Java

1static Node merge(Node a, Node b) {
2    Node dummy = new Node(0), tail = dummy;
3    while (a != null && b != null) {
4        if (a.val <= b.val) { tail.next = a; a = a.next; }
5        else                { tail.next = b; b = b.next; }
6        tail = tail.next;
7    }
8    tail.next = (a != null) ? a : b;
9    return dummy.next;
10}

Linked list merging: sorted merge, deduplicate, add two numbers

Interactive · edit the input

linked list · 6 nodes

null

∅

Being comparedLinked into the resultNew result node

Setup

Two sorted lists, A on the left and B on the right. A dummy tail starts the merged list; always take the smaller front node.

Step 1 / 13

Java

1static Node merge(Node a, Node b) {
2    Node dummy = new Node(0), tail = dummy;
3    while (a != null && b != null) {
4        if (a.val <= b.val) { tail.next = a; a = a.next; }      // take the smaller front node
5        else                { tail.next = b; b = b.next; }
6        tail = tail.next;
7    }
8    tail.next = (a != null) ? a : b;                            // append whichever list still has nodes
9    return dummy.next;
10}
11static Node deleteDuplicates(Node head) {
12    Node cur = head;
13    while (cur != null && cur.next != null) {
14        if (cur.val == cur.next.val) cur.next = cur.next.next;   // skip the duplicate
15        else cur = cur.next;
16    }
17    return head;
18}
19static Node addTwoNumbers(Node a, Node b) {                     // least significant digit first
20    Node dummy = new Node(0), tail = dummy; int carry = 0;
21    while (a != null || b != null || carry != 0) {
22        int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
23        tail.next = new Node(sum % 10); tail = tail.next; carry = sum / 10;
24        if (a != null) a = a.next;  if (b != null) b = b.next;
25    }
26    return dummy.next;
27}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	a=1 b=2	Two sorted lists, A on the left and B on the right. A dummy tail starts the merged list; always take the smaller front node.
2	L4	a=1 b=2	1 <= 2: take the node from A.
3	L6	a=3 b=2 merged=[1, 3, 5]	Linked 1 onto the merged list and advanced that list's pointer.
4	L4	a=3 b=2	3 > 2: take the node from B.
5	L6	a=3 b=4 merged=[1, 2, 4, 6]	Linked 2 onto the merged list and advanced that list's pointer.
6	L4	a=3 b=4	3 <= 4: take the node from A.
7	L6	a=5 b=4 merged=[1, 2, 3, 5]	Linked 3 onto the merged list and advanced that list's pointer.
8	L4	a=5 b=4	5 > 4: take the node from B.
9	L6	a=5 b=6 merged=[1, 2, 3, 4, 6]	Linked 4 onto the merged list and advanced that list's pointer.
10	L4	a=5 b=6	5 <= 6: take the node from A.
11	L6	a=null b=6 merged=[1, 2, 3, 4, 5]	Linked 5 onto the merged list and advanced that list's pointer.
12	L8	merged=[1, 2, 3, 4, 5, 6]	One list is empty: attach the other one's remaining nodes in a single step (they are already sorted and linked).
13	L9	return=[1, 2, 3, 4, 5, 6]	Merged: [1, 2, 3, 4, 5, 6]. No node was copied; only next pointers changed. O(n + m) time, O(1) extra space.

11.07.2

Merge k sorted lists

Merging k sorted lists with a min-heap: put the head of each list in a priority queue, repeatedly remove the smallest node, append it to the result and push its successor. With N total nodes the cost is O(N log k) time and O(k) extra space. Merging lists pairwise in a divide-and-conquer fashion gives the same bound.

The k-way merge animation shows the heap choosing the smallest front element.

Java

1static Node mergeK(Node[] lists) {
2    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt((Node n) -> n.val));
3    for (Node l : lists) if (l != null) pq.offer(l);
4    Node dummy = new Node(0), tail = dummy;
5    while (!pq.isEmpty()) {
6        Node n = pq.poll();
7        tail.next = n; tail = n;
8        if (n.next != null) pq.offer(n.next);
9    }
10    return dummy.next;
11}

K-way merge of sorted runs

Interactive · edit the input

run 0

7pos[0]

run 1

2pos[1]

run 2

5pos[2]

out[]

empty

Setup

3 sorted runs to merge. In an external sort these would be chunks that each fit in memory and were sorted separately, then written to disk.

Step 1 / 38

Java

1public static int[] kWayMerge(int[][] runs) {
2    int k = runs.length, total = 0;
3    for (int[] r : runs) total += r.length;
4    int[] pos = new int[k];                // next unread index in each run
5    int[] out = new int[total];
6    for (int o = 0; o < total; o++) {
7        int best = -1;
8        for (int r = 0; r < k; r++) {
9            if (pos[r] < runs[r].length &&
10                (best == -1 || runs[r][pos[r]] < runs[best][pos[best]])) {
11                best = r;
12            }
13        }
14        out[o] = runs[best][pos[best]++];
15    }
16    return out;
17}

Live state

0 comparisons

pos[0]

pos[1]

pos[2]

No condition evaluated on this step

Execution trace (dry run table)Show 38 steps

Step	Line	State	What happens
1	L4	o=0 pos[0]=0 pos[1]=0 pos[2]=0	3 sorted runs to merge. In an external sort these would be chunks that each fit in memory and were sorted separately, then written to disk.
2	L11	o=0 pos[0]=0 pos[1]=0 pos[2]=0 best=0 r=0	Run 0's head 7 is the first candidate.
3	L10	o=0 pos[0]=0 pos[1]=0 pos[2]=0 best=0 r=1	Run 1's head is smaller, so it becomes the new best.
4	L10	o=0 pos[0]=0 pos[1]=0 pos[2]=0 best=1 r=2	Run 1's head is still the smallest.
5	L14	o=1 pos[0]=0 pos[1]=1 pos[2]=0 best=1	out[0] = 2, taken from run 1.
6	L11	o=1 pos[0]=0 pos[1]=1 pos[2]=0 best=0 r=0	Run 0's head 7 is the first candidate.
7	L10	o=1 pos[0]=0 pos[1]=1 pos[2]=0 best=0 r=1	Run 0's head is still the smallest.
8	L10	o=1 pos[0]=0 pos[1]=1 pos[2]=0 best=0 r=2	Run 2's head is smaller, so it becomes the new best.
9	L14	o=2 pos[0]=0 pos[1]=1 pos[2]=1 best=2	out[1] = 5, taken from run 2.
10	L11	o=2 pos[0]=0 pos[1]=1 pos[2]=1 best=0 r=0	Run 0's head 7 is the first candidate.
11	L10	o=2 pos[0]=0 pos[1]=1 pos[2]=1 best=0 r=1	Run 0's head is still the smallest.
12	L10	o=2 pos[0]=0 pos[1]=1 pos[2]=1 best=0 r=2	Run 0's head is still the smallest.
13	L14	o=3 pos[0]=1 pos[1]=1 pos[2]=1 best=0	out[2] = 7, taken from run 0.
14	L11	o=3 pos[0]=1 pos[1]=1 pos[2]=1 best=0 r=0	Run 0's head 19 is the first candidate.
15	L10	o=3 pos[0]=1 pos[1]=1 pos[2]=1 best=0 r=1	Run 1's head is smaller, so it becomes the new best.
16	L10	o=3 pos[0]=1 pos[1]=1 pos[2]=1 best=1 r=2	Run 1's head is still the smallest.
17	L14	o=4 pos[0]=1 pos[1]=2 pos[2]=1 best=1	out[3] = 11, taken from run 1.
18	L11	o=4 pos[0]=1 pos[1]=2 pos[2]=1 best=0 r=0	Run 0's head 19 is the first candidate.
19	L10	o=4 pos[0]=1 pos[1]=2 pos[2]=1 best=0 r=1	Run 0's head is still the smallest.
20	L10	o=4 pos[0]=1 pos[1]=2 pos[2]=1 best=0 r=2	Run 0's head is still the smallest.
21	L14	o=5 pos[0]=2 pos[1]=2 pos[2]=1 best=0	out[4] = 19, taken from run 0.
22	L11	o=5 pos[0]=2 pos[1]=2 pos[2]=1 best=0 r=0	Run 0's head 34 is the first candidate.
23	L10	o=5 pos[0]=2 pos[1]=2 pos[2]=1 best=0 r=1	Run 1's head is smaller, so it becomes the new best.
24	L10	o=5 pos[0]=2 pos[1]=2 pos[2]=1 best=1 r=2	Run 2's head is smaller, so it becomes the new best.
25	L14	o=6 pos[0]=2 pos[1]=2 pos[2]=2 best=2	out[5] = 23, taken from run 2.
26	L11	o=6 pos[0]=2 pos[1]=2 pos[2]=2 best=0 r=0	Run 0's head 34 is the first candidate.
27	L10	o=6 pos[0]=2 pos[1]=2 pos[2]=2 best=0 r=1	Run 1's head is smaller, so it becomes the new best.
28	L10	o=6 pos[0]=2 pos[1]=2 pos[2]=2 best=1 r=2	Run 1's head is still the smallest.
29	L14	o=7 pos[0]=2 pos[1]=3 pos[2]=2 best=1	out[6] = 28, taken from run 1.
30	L11	o=7 pos[0]=2 pos[1]=3 pos[2]=2 best=0 r=0	Run 0's head 34 is the first candidate.
31	L9	o=7 pos[0]=2 pos[1]=3 pos[2]=2 best=0 r=1	Run 1 is exhausted, skip it.
32	L10	o=7 pos[0]=2 pos[1]=3 pos[2]=2 best=0 r=2	Run 0's head is still the smallest.
33	L14	o=8 pos[0]=3 pos[1]=3 pos[2]=2 best=0	out[7] = 34, taken from run 0.
34	L9	o=8 pos[0]=3 pos[1]=3 pos[2]=2 r=0	Run 0 is exhausted, skip it.
35	L9	o=8 pos[0]=3 pos[1]=3 pos[2]=2 r=1	Run 1 is exhausted, skip it.
36	L11	o=8 pos[0]=3 pos[1]=3 pos[2]=2 best=2 r=2	Run 2's head 40 is the first candidate.
37	L14	o=9 pos[0]=3 pos[1]=3 pos[2]=3 best=2	out[8] = 40, taken from run 2.
38	L16	return=[2, 5, 7, 11, 19, 23, 28, 34, 40]	Merged 9 values with 15 comparisons. Scanning k heads costs O(k) per value, so a min-heap of the heads makes it O(log k) and the total O(n log k).

11.07.3

Add two numbers

When digits are stored least significant first, adding two numbers is a single walk through both lists with a carry: sum = carry + a + b, write sum % 10, carry sum / 10, and keep going while either list or the carry remains. The result may be one node longer than the inputs. If the digits were stored most significant first, reverse the lists or use stacks.

Try 342 + 465 and the carry-out preset.

Java

1static Node addTwoNumbers(Node a, Node b) {
2    Node dummy = new Node(0), tail = dummy;
3    int carry = 0;
4    while (a != null || b != null || carry != 0) {
5        int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
6        tail.next = new Node(sum % 10); tail = tail.next;
7        carry = sum / 10;
8        if (a != null) a = a.next;
9        if (b != null) b = b.next;
10    }
11    return dummy.next;
12}

Linked list merging: sorted merge, deduplicate, add two numbers

Interactive · edit the input

linked list · 6 nodes

null

∅

Being comparedLinked into the resultNew result node

Setup

Two sorted lists, A on the left and B on the right. A dummy tail starts the merged list; always take the smaller front node.

Step 1 / 13

Java

1static Node merge(Node a, Node b) {
2    Node dummy = new Node(0), tail = dummy;
3    while (a != null && b != null) {
4        if (a.val <= b.val) { tail.next = a; a = a.next; }      // take the smaller front node
5        else                { tail.next = b; b = b.next; }
6        tail = tail.next;
7    }
8    tail.next = (a != null) ? a : b;                            // append whichever list still has nodes
9    return dummy.next;
10}
11static Node deleteDuplicates(Node head) {
12    Node cur = head;
13    while (cur != null && cur.next != null) {
14        if (cur.val == cur.next.val) cur.next = cur.next.next;   // skip the duplicate
15        else cur = cur.next;
16    }
17    return head;
18}
19static Node addTwoNumbers(Node a, Node b) {                     // least significant digit first
20    Node dummy = new Node(0), tail = dummy; int carry = 0;
21    while (a != null || b != null || carry != 0) {
22        int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
23        tail.next = new Node(sum % 10); tail = tail.next; carry = sum / 10;
24        if (a != null) a = a.next;  if (b != null) b = b.next;
25    }
26    return dummy.next;
27}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	a=1 b=2	Two sorted lists, A on the left and B on the right. A dummy tail starts the merged list; always take the smaller front node.
2	L4	a=1 b=2	1 <= 2: take the node from A.
3	L6	a=3 b=2 merged=[1, 3, 5]	Linked 1 onto the merged list and advanced that list's pointer.
4	L4	a=3 b=2	3 > 2: take the node from B.
5	L6	a=3 b=4 merged=[1, 2, 4, 6]	Linked 2 onto the merged list and advanced that list's pointer.
6	L4	a=3 b=4	3 <= 4: take the node from A.
7	L6	a=5 b=4 merged=[1, 2, 3, 5]	Linked 3 onto the merged list and advanced that list's pointer.
8	L4	a=5 b=4	5 > 4: take the node from B.
9	L6	a=5 b=6 merged=[1, 2, 3, 4, 6]	Linked 4 onto the merged list and advanced that list's pointer.
10	L4	a=5 b=6	5 <= 6: take the node from A.
11	L6	a=null b=6 merged=[1, 2, 3, 4, 5]	Linked 5 onto the merged list and advanced that list's pointer.
12	L8	merged=[1, 2, 3, 4, 5, 6]	One list is empty: attach the other one's remaining nodes in a single step (they are already sorted and linked).
13	L9	return=[1, 2, 3, 4, 5, 6]	Merged: [1, 2, 3, 4, 5, 6]. No node was copied; only next pointers changed. O(n + m) time, O(1) extra space.

11.07.4

Intersection of lists

Two lists can merge into a shared tail (the same nodes, not just equal values). To find the first shared node without extra memory, walk two pointers and when one reaches the end, restart it at the head of the other list. Both pointers then travel lenA + lenB nodes and meet at the intersection, or both reach null together if there is none. O(n + m) time, O(1) space.

No animation here: the diagram is a Y-shape with a shared tail, which a single row of nodes cannot show faithfully.

Java

1static Node intersection(Node a, Node b) {
2    Node p = a, q = b;
3    while (p != q) {
4        p = (p == null) ? b : p.next;        // after A, continue on B
5        q = (q == null) ? a : q.next;        // after B, continue on A
6    }
7    return p;                                 // the shared node, or null
8}

11.07.5

Deduplicate sorted lists

In a sorted list equal values are adjacent. Walk with cur: if cur.val == cur.next.val, bypass the duplicate with cur.next = cur.next.next; otherwise advance. O(n) time, O(1) space. To remove every value that appears more than once (not just the extra copies), use a dummy head and skip whole runs.

Run the deduplicate task in the merge animation.

Java

1static Node deleteDuplicates(Node head) {
2    Node cur = head;
3    while (cur != null && cur.next != null) {
4        if (cur.val == cur.next.val) cur.next = cur.next.next;
5        else cur = cur.next;
6    }
7    return head;
8}

Linked list merging: sorted merge, deduplicate, add two numbers

Interactive · edit the input

linked list · 6 nodes

null

∅

Being comparedLinked into the resultNew result node

Setup

Two sorted lists, A on the left and B on the right. A dummy tail starts the merged list; always take the smaller front node.

Step 1 / 13

Java

1static Node merge(Node a, Node b) {
2    Node dummy = new Node(0), tail = dummy;
3    while (a != null && b != null) {
4        if (a.val <= b.val) { tail.next = a; a = a.next; }      // take the smaller front node
5        else                { tail.next = b; b = b.next; }
6        tail = tail.next;
7    }
8    tail.next = (a != null) ? a : b;                            // append whichever list still has nodes
9    return dummy.next;
10}
11static Node deleteDuplicates(Node head) {
12    Node cur = head;
13    while (cur != null && cur.next != null) {
14        if (cur.val == cur.next.val) cur.next = cur.next.next;   // skip the duplicate
15        else cur = cur.next;
16    }
17    return head;
18}
19static Node addTwoNumbers(Node a, Node b) {                     // least significant digit first
20    Node dummy = new Node(0), tail = dummy; int carry = 0;
21    while (a != null || b != null || carry != 0) {
22        int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0);
23        tail.next = new Node(sum % 10); tail = tail.next; carry = sum / 10;
24        if (a != null) a = a.next;  if (b != null) b = b.next;
25    }
26    return dummy.next;
27}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	a=1 b=2	Two sorted lists, A on the left and B on the right. A dummy tail starts the merged list; always take the smaller front node.
2	L4	a=1 b=2	1 <= 2: take the node from A.
3	L6	a=3 b=2 merged=[1, 3, 5]	Linked 1 onto the merged list and advanced that list's pointer.
4	L4	a=3 b=2	3 > 2: take the node from B.
5	L6	a=3 b=4 merged=[1, 2, 4, 6]	Linked 2 onto the merged list and advanced that list's pointer.
6	L4	a=3 b=4	3 <= 4: take the node from A.
7	L6	a=5 b=4 merged=[1, 2, 3, 5]	Linked 3 onto the merged list and advanced that list's pointer.
8	L4	a=5 b=4	5 > 4: take the node from B.
9	L6	a=5 b=6 merged=[1, 2, 3, 4, 6]	Linked 4 onto the merged list and advanced that list's pointer.
10	L4	a=5 b=6	5 <= 6: take the node from A.
11	L6	a=null b=6 merged=[1, 2, 3, 4, 5]	Linked 5 onto the merged list and advanced that list's pointer.
12	L8	merged=[1, 2, 3, 4, 5, 6]	One list is empty: attach the other one's remaining nodes in a single step (they are already sorted and linked).
13	L9	return=[1, 2, 3, 4, 5, 6]	Merged: [1, 2, 3, 4, 5, 6]. No node was copied; only next pointers changed. O(n + m) time, O(1) extra space.

Practice ladder

Now try it yourself

Easy

Merge 1 → 3 → 5 and 2 → 4 → 6 by hand
Deduplicate 1 → 1 → 2 → 3 → 3

Medium

Add 342 and 465 stored as 2 → 4 → 3 and 5 → 6 → 4
Find the intersection node of two lists that share a tail

Advanced

Merge k sorted lists in O(N log k) and explain the heap size

Key takeaways

Merging relinks nodes with a dummy head: O(n + m), O(1) space.
A heap merges k lists in O(N log k).
Swap pointers between lists to find an intersection without extra memory.