Merging and Splitting Linked Lists
Rearranging is relinking
Deal a deck of cards into two piles and gather them back. No card is copied and none is made; each one moves once, onto the top of a pile. Merging two sorted lists, splitting one by position or by value, adding two numbers stored as lists, rotating, reordering and sorting a list are all that deal: take a node off the input and link it onto an output list.
The first answer most people reach for copies the values out instead:
def merge_by_copy(a, b):
values = []
for head in (a, b):
while head is not None:
values.append(head.val)
head = head.next
values.sort()
dummy = tail = Node(0)
for v in values: # a new node for every value
tail.next = Node(v)
tail = tail.next
return dummy.next
For 1 → 2 → 4 and 1 → 3 → 4 it returned 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null, and it made 7 new nodes (six for the values and a dummy). Linking the existing nodes made 1: the dummy. Copying costs O(n) extra space and hands back different nodes, which matters when other code holds on to them.
The tool for relinking is a tail: the last node of the list you're building. The output starts at a dummy, so the tail always exists, and appending is two writes, tail.next = node and tail = node. One tail per output list: one to merge, two to split.
Merging two sorted lists
Merge Two Sorted Lists keeps a tail on the merged list. While both lists have nodes, compare their heads, append the smaller, and move that list on. When one list runs out, the rest of the other is already sorted and already linked together, so one write attaches all of it.
Merge 1 → 3 and 1 → 2 — The dashed box is the merged list's dummy. Each step moves one node down to the merged row; the green arrow is the link just written.
Node* mergeTwoLists(Node* a, Node* b) {
Node dummy(0); // the merged list starts here
Node* tail = &dummy;
while (a != nullptr && b != nullptr) {
if (a->val <= b->val) { // on a tie take a's node: equal values keep their order
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next; // the node just appended is the new tail
}
tail->next = a != nullptr ? a : b; // one list is empty: one write attaches the rest
return dummy.next;
}
def merge_two_lists(a, b):
dummy = Node(0) # the merged list starts here
tail = dummy
while a is not None and b is not None:
if a.val <= b.val: # on a tie take a's node: equal values keep their order
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next # the node just appended is the new tail
tail.next = a if a is not None else b # one list is empty: one write attaches the rest
return dummy.next
static Node mergeTwoLists(Node a, Node b) {
Node dummy = new Node(0, null); // the merged list starts here
Node tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { // on a tie take a's node: equal values keep their order
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next; // the node just appended is the new tail
}
tail.next = a != null ? a : b; // one list is empty: one write attaches the rest
return dummy.next;
}
function mergeTwoLists(a, b) {
const dummy = new Node(0); // the merged list starts here
let tail = dummy;
while (a !== null && b !== null) {
if (a.val <= b.val) { // on a tie take a's node: equal values keep their order
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next; // the node just appended is the new tail
}
tail.next = a !== null ? a : b; // one list is empty: one write attaches the rest
return dummy.next;
}
Each printed 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null, 1 -> 2 -> 3 -> 5 -> 6 -> 9 -> null (b ran out first, and one write attached 5, 6 and 9), 0 -> null and null. On a tie the code takes a's node: for 1 → 3 and 1 → 2 the merged list started with a's 1 (merge_two_lists(a, b) is a printed True). Keeping equal values in their input order makes the merge stable, which Sort List below relies on. O(m + n) time, O(1) extra space.
Splitting: one tail per pile, then join and cut
Odd Even Linked List puts the nodes at odd positions first, then the even ones, each group in its order. Deal the list into two piles, each with its own dummy and tail, then join the odd pile's tail to the even pile's head.
One write is easy to miss. A node appended to a pile keeps its old next until the next append to that pile overwrites it, and the last node of a pile never gets another append. So the last pile's tail still points back into the old list. Cut it.
Deal 1 to 5 into two piles — Dashed boxes are the piles' dummies. A dim dashed arrow is a next that still points into the input; the red one is the link that would make the list loop.
Node* oddEvenList(Node* head) {
Node oddDummy(0), evenDummy(0);
Node* odd = &oddDummy; // one tail per pile
Node* even = &evenDummy;
for (int position = 1; head != nullptr; position++) {
if (position % 2 == 1) {
odd->next = head;
odd = head;
} else {
even->next = head;
even = head;
}
head = head->next;
}
even->next = nullptr; // cut: the last even node still points into the input
odd->next = evenDummy.next; // join: the odd pile, then the even pile
return oddDummy.next;
}
def odd_even_list(head):
odd_dummy, even_dummy = Node(0), Node(0)
odd, even = odd_dummy, even_dummy # one tail per pile
position = 1
while head is not None:
if position % 2 == 1:
odd.next = head
odd = head
else:
even.next = head
even = head
head = head.next
position += 1
even.next = None # cut: the last even node still points into the input
odd.next = even_dummy.next # join: the odd pile, then the even pile
return odd_dummy.next
static Node oddEvenList(Node head) {
Node oddDummy = new Node(0, null), evenDummy = new Node(0, null);
Node odd = oddDummy; // one tail per pile
Node even = evenDummy;
for (int position = 1; head != null; position++) {
if (position % 2 == 1) {
odd.next = head;
odd = head;
} else {
even.next = head;
even = head;
}
head = head.next;
}
even.next = null; // cut: the last even node still points into the input
odd.next = evenDummy.next; // join: the odd pile, then the even pile
return oddDummy.next;
}
function oddEvenList(head) {
const oddDummy = new Node(0), evenDummy = new Node(0);
let odd = oddDummy; // one tail per pile
let even = evenDummy;
for (let position = 1; head !== null; position++) {
if (position % 2 === 1) {
odd.next = head;
odd = head;
} else {
even.next = head;
even = head;
}
head = head.next;
}
even.next = null; // cut: the last even node still points into the input
odd.next = evenDummy.next; // join: the odd pile, then the even pile
return oddDummy.next;
}
Each printed 1 -> 3 -> 5 -> 2 -> 4 -> null, 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4 -> null, 1 -> null and null. Without even.next = None, 4 kept pointing to 5, and the list read 1 -> 3 -> 5 -> 2 -> 4 -> 5 -> 2 -> 4 -> 5 -> 2 -> 4 -> 5 -> 2 -> 4 -> ...: 1, 3, 5, 2, 4, then 5 again, round and round.
Splitting by value is the same deal with a different rule. Our sheet's Partition a Linked List around a given value wants three groups, less than x, equal and greater, each in its input order: three piles, joined from the back, and the last one cut.
def partition(head, x):
less_dummy, equal_dummy, more_dummy = Node(0), Node(0), Node(0)
less, equal, more = less_dummy, equal_dummy, more_dummy # three piles, each in input order
while head is not None:
if head.val < x:
less.next = head
less = head
elif head.val == x:
equal.next = head
equal = head
else:
more.next = head
more = head
head = head.next
more.next = None # cut the last pile
equal.next = more_dummy.next # join from the back: equal, then more
less.next = equal_dummy.next # less, then equal
return less_dummy.next
It returned 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 5 -> null for 1, 4, 3, 2, 5, 2, 3 around 3, 1 -> 2 -> 4 -> 10 -> null for 1, 4, 2, 10 around 3 (no node equals 3, so that pile stays empty) and 1 -> 5 -> null for 5, 1 around 5.
Now you stitch them
Below, you do the dealing. In the merge tasks, pick the head that goes next; a pick that would break the order is refused with the reason, and when one list is empty you can attach the rest in one write. In the split tasks, send each node to its pile, then join the piles and decide whether to cut: read the list without the cut and you'll watch the walk go round. Dim dashed arrows are nexts that still point where they did in the input.
Adding two numbers, digit by digit
Add Two Numbers stores each number's digits in a list, ones digit first, so 342 is 2 → 4 → 3. Walk both lists together like column addition: add the two digits and the carry, append the ones digit to the answer's tail, carry the tens. The answer is the one list here made of new nodes.
def add_two_numbers(a, b):
dummy = Node(0)
tail = dummy
carry = 0
while a is not None or b is not None or carry: # a carry left over is one more digit
total = carry
if a is not None:
total += a.val
a = a.next
if b is not None:
total += b.val
b = b.next
carry, digit = divmod(total, 10)
tail.next = Node(digit) # the answer's digits are the only new nodes
tail = tail.next
return dummy.next
2 → 4 → 3 plus 5 → 6 → 4 (342 + 465) returned 7 -> 0 -> 8 -> null, 807. 9,999,999 + 9,999 returned 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1 -> null: the carry ran past both lists and added the last digit, 1. 0 + 0 returned 0 -> null.
Rotate: close the ring, then cut it
Rotate List moves the last k nodes to the front. Rotating by the length changes nothing, so k only matters modulo the length n. One walk finds n and the last node; link the last node to the head, which closes a ring; walk n − k − 1 nodes from the head to the new last node, and cut after it.
def rotate_right(head, k):
if head is None:
return None
n, tail = 1, head
while tail.next is not None: # one walk for the length and the last node
tail = tail.next
n += 1
k %= n # n rotations change nothing
if k == 0:
return head
tail.next = head # close the ring
new_tail = head
for _ in range(n - k - 1): # the new last node is n - k - 1 steps from the head
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None # and cut it there
return new_head
It returned 4 -> 5 -> 1 -> 2 -> 3 -> null for 1 to 5 rotated by 2, 2 -> 0 -> 1 -> null for 0, 1, 2 by 4 (4 mod 3 is 1), and 4 -> 5 -> 1 -> 2 -> 3 -> null for 1 to 5 by 2,000,000,002, the same as by 2. Moving the last node to the front once per rotation got the same answer for 200,000 rotations of 100 nodes, in 1,432 ms; closing the ring took 0.076 ms.
Reorder List: middle, reverse, weave
Reorder List turns 1, 2, …, n into 1, n, 2, n − 1, …. It's three steps from this section: find the first middle (Fast and Slow Pointers) and cut after it, reverse the second half (Reversing a Linked List), then weave the halves together, one node from each.
def reorder_list(head):
if head is None or head.next is None:
return head
slow, fast = head, head.next # 1. the first middle
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None # cut after the middle
prev = None
while second is not None: # 2. reverse the second half
nxt = second.next
second.next = prev
prev = second
second = nxt
first, second = head, prev
while second is not None: # 3. weave: one from each half
n1, n2 = first.next, second.next
first.next = second
second.next = n1
first, second = n1, n2
return head
It turned 1 → 2 → 3 → 4 into 1 -> 4 -> 2 -> 3 -> null and 1 → 2 → 3 → 4 → 5 into 1 -> 5 -> 2 -> 4 -> 3 -> null. Forget the cut after the middle and the first half's last node still points into the reversed half: 1 → 2 → 3 → 4 came back as 1 -> 4 -> 2 -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 -> ....
Sort List: merge sort without an array
Sort List sorts a list in O(n log n). Merge sort fits a list well: split it at the middle, sort each half, merge. Splitting needs no copying, just fast and slow to find the middle and one cut, and the merge is the one above. Use the first middle, so a two-node list splits into one and one.
Node* sortList(Node* head) {
if (head == nullptr || head->next == nullptr) return head; // zero or one node: sorted
Node* slow = head;
Node* fast = head->next; // the first middle, so two nodes split one and one
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
Node* right = slow->next;
slow->next = nullptr; // cut the list in two
return mergeTwoLists(sortList(head), sortList(right));
}
def sort_list(head):
if head is None or head.next is None: # zero or one node: sorted
return head
slow, fast = head, head.next # the first middle, so two nodes split one and one
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
right = slow.next
slow.next = None # cut the list in two
return merge_two_lists(sort_list(head), sort_list(right))
static Node sortList(Node head) {
if (head == null || head.next == null) return head; // zero or one node: sorted
Node slow = head;
Node fast = head.next; // the first middle, so two nodes split one and one
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Node right = slow.next;
slow.next = null; // cut the list in two
return mergeTwoLists(sortList(head), sortList(right));
}
function sortList(head) {
if (head === null || head.next === null) return head; // zero or one node: sorted
let slow = head;
let fast = head.next; // the first middle, so two nodes split one and one
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
const right = slow.next;
slow.next = null; // cut the list in two
return mergeTwoLists(sortList(head), sortList(right));
}
With merge_two_lists from above, each printed 1 -> 2 -> 3 -> 4 -> null, -1 -> 0 -> 3 -> 4 -> 5 -> null, 1 -> null and null. The recursion is log n deep, so O(log n) extra space.
Is it faster than copying the values into an array, sorting that, and writing them back? No. On our judge, 200,000 nodes in Python took 1,198 ms against 152 ms, and 1,000,000 scattered nodes in C++ took 1,318 ms against 302 ms. An array's values sit together in memory, so sorting it is fast (the cache run in Introduction to Linked Lists shows why). The list version is the one that needs no array, which is what the problem asks.
Copy List with Random Pointer: weave, set, unweave
Copy List with Random Pointer gives each node a second pointer, random, to any node or null, and asks for a deep copy. The hard part is a copy's random: it must point at the copy of the original's random, and that copy may not exist yet. A map from each original to its copy solves it in O(n) extra space. Weaving needs none:
- put each node's copy right after it: 7 → 7′ → 13 → 13′ → …;
- now the copy of any node is that node's
next, so a copy's random isoriginal.random.next; - unweave: link the copies into their own list and give each original its
nextback.
class RNode:
def __init__(self, val, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copy_random_list(head):
curr = head
while curr is not None: # 1. weave: a copy right after each node
curr.next = RNode(curr.val, curr.next)
curr = curr.next.next
curr = head
while curr is not None: # 2. a copy's random is the copy of the original's random
if curr.random is not None:
curr.next.random = curr.random.next
curr = curr.next.next
dummy = tail = RNode(0)
curr = head
while curr is not None: # 3. unweave: copies to their own list, originals get next back
copy = curr.next
curr.next = copy.next
tail.next = copy
tail = copy
curr = curr.next
return dummy.next
On LeetCode's example, nodes 7, 13, 11, 10, 1 with randoms to positions none, 0, 4, 2, 0, the copy read [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] as [value, random's position], the original read the same as before (True), and no node was shared between the two lists (shared printed False).
Spotting it, and when it breaks
The clues. The output is the input's nodes in another order: merge, interleave, group by a rule, rotate, sort. Anything that builds a list front to back: digits of a sum, a filtered list. The words "without new nodes" or "in place".
The near-misses. Merging many lists at once is Merge k Sorted Lists, in Heaps: a heap picks the smallest of k heads. And when the problem allows O(n) space and speed matters more than the list, copying to an array is honestly faster, as the timing above shows.
When it breaks. Every output list's last node needs its next set: to the next pile when joining, to null at the very end. A pile that's empty still has its dummy, so joining stays one write.
Bugs that cost a submission
Not cutting the last tail. Odd Even without even.next = None read 1 -> 3 -> 5 -> 2 -> 4 -> 5 -> 2 -> 4 -> 5 -> 2 -> 4 -> 5 -> 2 -> 4 -> .... Partition and Reorder List fail the same way; Reorder List without the cut after the middle read 1 -> 4 -> 2 -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 -> ....
Dropping the rest of a merge. This version stops as soon as one list runs out:
def merge_two_lists(a, b):
dummy = Node(0) # the merged list starts here
tail = dummy
while a is not None and b is not None:
if a.val <= b.val: # on a tie take a's node: equal values keep their order
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next # the node just appended is the new tail
return dummy.next
For 1 → 2 → 4 and 1 → 3 → 4 → 8 → 9 it returned 1 -> 1 -> 2 -> 3 -> 4 -> null: 4, 8 and 9 were never attached.
Dropping the last carry. Add Two Numbers looping only while a list has digits:
def add_two_numbers(a, b):
dummy = Node(0)
tail = dummy
carry = 0
while a is not None or b is not None: # stops with a carry still in hand
total = carry
if a is not None:
total += a.val
a = a.next
if b is not None:
total += b.val
b = b.next
carry, digit = divmod(total, 10)
tail.next = Node(digit) # the answer's digits are the only new nodes
tail = tail.next
return dummy.next
9,999,999 + 9,999 came out as 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> null, missing the final 1, and 5 + 5 as 0 -> null, not 0 -> 1 -> null.
The second middle in Sort List.
def sort_list(head):
if head is None or head.next is None: # zero or one node: sorted
return head
slow, fast = head, head # the second middle: two nodes never split
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
right = slow.next
slow.next = None # cut the list in two
return merge_two_lists(sort_list(head), sort_list(right))
On 2 → 1, slow stops on the second node, the cut leaves the left half as both nodes, and it never gets smaller: Python raised RecursionError.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
even.next = None. What does the list read?Multiple choice
while a or b. What does 5 + 5 return?Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Merge Two Sorted Lists: one tail, the smaller head, then attach the rest.
- Odd Even Linked List: two piles by position, join, cut.
- Partition a Linked List around a given value: three piles by value.
- Add Two Numbers: the same tail, with a carry.
- Rotate List: k mod n, close the ring, cut.
- Reorder List: middle, reverse, weave.
- Sort List: the first middle, cut, sort both, merge.
- Copy List with Random Pointer: weave, set, unweave.
That's the last Linked List lesson. Next, the section quiz, then Stacks.