DSA for Interviews, From Zero

Part 9 · Lesson 37 · read

Merging and Cycle Problems

Join sorted lists, find where a loop starts, and remove the nth node from the end.

On this page

  1. Merging two sorted lists
  2. Traced: merging 1 → 3 → 5 with 2 → 4
  3. Where a cycle starts
  4. Remove the n-th node from the end
  5. Where two lists meet
  6. Adding two numbers stored in lists
  7. Sorting a list with merge sort
  8. Practice questions (7)
  9. Make it stick
  10. What's next

Merging two sorted lists

A linked list is a chain of small objects called nodes. Each node holds a value and a link (next) to the following node. A pointer here just means a variable that holds one node, so it "points" at a place in the chain. Merging means joining two sorted lists into one sorted list. You already merged two sorted arrays in the sorting part. With linked lists the idea is the same, but it is even neater. You do not copy anything. You just change the links of the existing nodes to put them in the right order. A dummy head and a tail pointer keep the code short. The dummy is a fake first node that you throw away at the end. It means attaching the first real node is no different from attaching any other.

JavaScript
function mergeTwoLists(a, b) {  const dummy = new ListNode(0);  let tail = dummy;                       // tail is where the next node will be attached  while (a !== null && b !== null) {    if (a.val <= b.val) { tail.next = a; a = a.next; }    else                { tail.next = b; b = b.next; }    tail = tail.next;  }  tail.next = a !== null ? a : b;         // one list is used up: attach what is left of the other  return dummy.next;}console.log(toArray(mergeTwoLists(fromArray([1, 3, 5]), fromArray([2, 4])))); // [1, 2, 3, 4, 5]console.log(toArray(mergeTwoLists(fromArray([]), fromArray([0]))));           // [0]

Traced: merging 1 → 3 → 5 with 2 → 4

step 1 / 12
Set up
dummy = ListNode(0), tail = dummy

The dummy node is a fake first node. It means attaching the very first real node is no different from attaching any other. tail marks where to attach the next node.

▶const dummy = new ListNode(0);2let tail = dummy;3while (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}8tail.next = a !== null ? a : b;9return dummy.next;
Variables
a[1, 3, 5]
b[2, 4]
merged[]
Console
(nothing printed yet)
Always attach the smaller front node. When one list runs out, attach the other list's remainder in one move. · interactive

Time is O(m + n) (m and n are the two list lengths, and every node is attached once). Extra space is O(1). Using <= instead of < keeps the merge stable. Stable means that equal values from the first list stay ahead of equal values from the second list.

Where a cycle starts

A cycle is a loop in a linked list: some node's next points back to an earlier node, so the chain never ends. Floyd's algorithm (also called tortoise and hare) is a method that finds a cycle with two pointers. The slow one moves 1 node per step and the fast one moves 2 nodes per step. If there is a cycle, they must meet inside it.

Lesson 36 checked whether there is a cycle. To find where it begins, add a second phase. When slow and fast first meet, leave slow where it is and put a new pointer at the head. Move both one step at a time. They meet at the first node of the cycle.

JavaScript
function detectCycle(head) {  let slow = head, fast = head;  while (fast !== null && fast.next !== null) {    slow = slow.next;    fast = fast.next.next;    if (slow === fast) {                 // phase 1: they met inside the loop      let p = head;                      // phase 2: restart one pointer from the head      while (p !== slow) { p = p.next; slow = slow.next; }      return p;                          // both now stand on the first node of the loop    }  }  return null;                           // no cycle}const list = fromArray([3, 2, 0, -4, 7]);list.next.next.next.next.next = list.next;   // the tail points back at the node holding 2console.log(detectCycle(list).val);          // 2console.log(detectCycle(fromArray([1, 2])));  // null

Why it works. Let the straight part before the loop have length a. Let the meeting point be b steps into the loop, and let the loop have length c. Slow has walked a + b steps. Fast has walked twice as many. Fast is at the same node as slow, so it must have walked some whole number of extra laps (call it k). That gives 2(a + b) = a + b + k·c, so a + b = k·c, which means a = k·c − b. Now start at the meeting point and walk a more steps. You end at the loop start (k laps, minus the b steps already covered). The pointer from the head also walks asteps and lands at the loop start. So they arrive together.

Remove the n-th node from the end

You do not know the length, and you want to delete a node counted from the back. Use a gap. First, send fast n nodes ahead. Then move both pointers together. The gap between them never changes. So when fast is on the last node, slow is exactly one node before the node to delete. Start both at a dummy head. Then removing the real head works too.

JavaScript
function removeNthFromEnd(head, n) {  const dummy = new ListNode(0, head);  let fast = dummy, slow = dummy;  for (let i = 0; i < n; i++) fast = fast.next;     // open a gap of n nodes  while (fast.next !== null) {                      // move both until fast is on the LAST node    fast = fast.next;    slow = slow.next;  }  slow.next = slow.next.next;                       // slow is just before the node to delete  return dummy.next;}console.log(toArray(removeNthFromEnd(fromArray([1, 2, 3, 4, 5]), 2))); // [1, 2, 3, 5]console.log(toArray(removeNthFromEnd(fromArray([1]), 1)));             // []
Dry run · remove the 2nd from the end of 1 → 2 → 3 → 4 → 5
Momentslowfast
startdummydummy
after moving fast 2 stepsdummy2
fast.next exists: move both13
again24
again35
fast.next is null: stop. slow.next (4) is deleted35

The result is 1 → 2 → 3 → 5. Fast sets a fixed distance. Slow always stays that far behind fast.

Where two lists meet

Two lists can share their tails. This means the same node objects, not just equal values. Here is the trick. Walk pointer p along list A and then along list B. Walk q along list B and then along list A. Both walk the same total distance, len(A) + len(B). So they arrive at the shared node at the same moment. If the lists never share a node, both pointers reach null together, and the loop ends with null.

JavaScript
function getIntersectionNode(a, b) {  let p = a, q = b;  while (p !== q) {    p = p === null ? b : p.next;      // after finishing one list, continue on the other    q = q === null ? a : q.next;  }  return p;                           // the shared node, or null if they never meet}// 1 -> 2 -> 8 -> 9   and   5 -> 8 -> 9   (8 is shared)const shared = fromArray([8, 9]);const x = new ListNode(1, new ListNode(2, shared));const y = new ListNode(5, shared);console.log(getIntersectionNode(x, y).val);                    // 8console.log(getIntersectionNode(fromArray([1]), fromArray([2]))); // null
Same node, not same value
Two lists meet only if they share the same object. So compare the nodes with ===. If you compare val, you would wrongly match two separate lists that just happen to contain equal numbers.

Adding two numbers held in lists

Each list holds one digit per node, with the smallest place first (the ones digit comes first). So adding works like the addition you learned at school. You go from left to right and keep a carry (the extra 1 you carry to the next digit). Keep going while either list has digits or there is a carry left. If you stop too early, 99 + 1 would lose its final 1.

JavaScript
// Digits are stored in reverse order: 342 is 2 -> 4 -> 3.function addTwoNumbers(a, b) {  const dummy = new ListNode(0);  let tail = dummy, carry = 0;  while (a !== null || b !== null || carry > 0) {    const sum = (a ? a.val : 0) + (b ? b.val : 0) + carry;    tail.next = new ListNode(sum % 10);    carry = Math.floor(sum / 10);    tail = tail.next;    if (a) a = a.next;    if (b) b = b.next;  }  return dummy.next;}console.log(toArray(addTwoNumbers(fromArray([2, 4, 3]), fromArray([5, 6, 4])))); // [7, 0, 8]  (342 + 465 = 807)console.log(toArray(addTwoNumbers(fromArray([9, 9]), fromArray([1]))));          // [0, 0, 1]  (99 + 1 = 100)

Sorting a list with merge sort

Merge sort is a sorting algorithm that splits the list into two halves, sorts each half (by calling itself), and then merges the two sorted halves. A list of 0 or 1 nodes is already sorted, so that is where the splitting stops. Merge sort works well on linked lists. Finding the middle uses the slow and fast trick. Splitting takes one pointer change. Merging needs no extra array. It runs in O(n log n) time. Binary search is a poor fit for lists, because it needs random access, which means jumping straight to any position. A linked list cannot do that. Array-style quick sort, which swaps items by position, has the same problem.

JavaScript
function mergeTwoLists(a, b) {  const dummy = new ListNode(0);  let tail = dummy;  while (a !== null && b !== null) {    if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }    tail = tail.next;  }  tail.next = a !== null ? a : b;  return dummy.next;}function sortList(head) {  if (head === null || head.next === null) return head;     // 0 or 1 node: sorted  // find the end of the first half (slow stops BEFORE the middle)  let slow = head, fast = head.next;  while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; }  const second = slow.next;  slow.next = null;                                          // cut the list in two  return mergeTwoLists(sortList(head), sortList(second));}console.log(toArray(sortList(fromArray([4, 2, 1, 3]))));    // [1, 2, 3, 4]console.log(toArray(sortList(fromArray([-1, 5, 3, 4, 0])))); // [-1, 0, 3, 4, 5]
Why fast starts at head.next
Take the two-node list [1, 2]. If both pointers start at head, slow ends on the second node. Then the first half would be both nodes and the second half would be empty. The recursion would never get smaller. If fast starts one step ahead, slow stops on the last node of the first half. Then both halves are always smaller.

Practice questions

All of these use the same tools: a dummy head, a trailing pointer, slow and fast pointers, and careful changes to the links.

Q1Merge two sorted listsEasy

Join two sorted linked lists into one sorted list by changing the links of their nodes. Return its head.

Example 1
Input: [1, 2, 4] and [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: Always take the smaller front node.
Example 2
Input: [] and [0]
Output: [0]
Explanation: An empty list adds nothing.
Stuck? Open one hint at a time
Hint 1
Compare the two front nodes and attach the smaller one. A dummy head (a fake first node) means the first node needs no special handling.
Hint 2
When one list ends, you can attach the whole of the other list.
Show all 2 solutions with explanations
Approach 1Iterative with a dummy head
The idea

Keep a tail. Attach the smaller front node, move that list forward, and move tail forward. At the end, attach whatever is left.

JavaScript
function mergeTwoLists(a, b) {  const dummy = new ListNode(0);  let tail = dummy;  while (a !== null && b !== null) {    if (a.val <= b.val) { tail.next = a; a = a.next; }    else { tail.next = b; b = b.next; }    tail = tail.next;  }  tail.next = a !== null ? a : b;  return dummy.next;}console.log(toArray(mergeTwoLists(fromArray([1, 2, 4]), fromArray([1, 3, 4])))); // [1, 1, 2, 3, 4, 4]console.log(toArray(mergeTwoLists(fromArray([]), fromArray([0]))));              // [0]
How it works

O(m + n) time, O(1) space.

Approach 2Recursive
The idea

The smaller head stays at the front. Its next becomes the merge of the rest.

JavaScript
function mergeTwoLists(a, b) {  if (a === null) return b;  if (b === null) return a;  if (a.val <= b.val) { a.next = mergeTwoLists(a.next, b); return a; }  b.next = mergeTwoLists(a, b.next);  return b;}console.log(toArray(mergeTwoLists(fromArray([1, 2, 4]), fromArray([1, 3, 4])))); // [1, 1, 2, 3, 4, 4]
How it works

The code is very short, but it uses O(m + n) stack space (memory for unfinished function calls).

Which approach should you use?

Use the loop version for real-world code. The recursive version is a good second answer. (LeetCode 21.)

Q2Linked list cycle IIMedium

Return the node where the cycle begins, or null if there is no cycle.

Example 1
Input: [3, 2, 0, -4], tail points to the node with value 2
Output: node 2
Explanation: The loop starts at the second node.
Example 2
Input: [1, 2], no loop
Output: null
Explanation: There is no cycle.
Stuck? Open one hint at a time
Hint 1
First, use slow and fast pointers to check that a cycle exists. The place where they meet is somewhere inside the loop.
Hint 2
Start one pointer at the head and one at the meeting point. Move them at the same speed. They meet at the start of the loop.
Show all 2 solutions with explanations
Approach 1Set of visited nodes
The idea

A Set is a collection that keeps each item once and can check quickly whether an item is inside. Walk the list and add each node to the Set. The first node that you reach a second time is the start of the cycle.

JavaScript
function detectCycle(head) {  const seen = new Set();  for (let c = head; c !== null; c = c.next) {    if (seen.has(c)) return c;    seen.add(c);  }  return null;}const a = fromArray([3, 2, 0, -4]);a.next.next.next.next = a.next;console.log(detectCycle(a).val);          // 2console.log(detectCycle(fromArray([1]))); // null
How it works

O(n) time and O(n) space.

Approach 2Floyd's two phases (slow and fast pointers)
The idea
  1. Move slow and fast until they meet. If they never meet, there is no cycle.
  2. Start a pointer at the head. Move it and slow one step at a time until they are at the same node.
JavaScript
function detectCycle(head) {  let slow = head, fast = head;  while (fast !== null && fast.next !== null) {    slow = slow.next;    fast = fast.next.next;    if (slow === fast) {      let p = head;      while (p !== slow) { p = p.next; slow = slow.next; }      return p;    }  }  return null;}const a = fromArray([3, 2, 0, -4]);a.next.next.next.next = a.next;console.log(detectCycle(a).val); // 2
How it works

O(n) time, O(1) space. The distance from the head to the loop start is the same as the distance from the meeting point to the loop start, if you ignore whole laps around the loop. (The proof is in the lesson.)

Which approach should you use?

Start with the Set. Switch to Floyd's version when the interviewer asks for O(1) space. (LeetCode 142.)

Q3Remove Nth node from end of listMedium

Remove the n-th node counted from the end of the list and return the head. Assume n is valid.

Example 1
Input: [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Explanation: 4 is the second node from the end.
Example 2
Input: [1], n = 1
Output: []
Explanation: The only node is removed.
Example 3
Input: [1, 2], n = 2
Output: [2]
Explanation: The head is removed.
Stuck? Open one hint at a time
Hint 1
Removing the head must work too. Which trick makes the head act like any other node?
Hint 2
If one pointer is n nodes ahead of another, where is the second pointer when the first one reaches the end?
Show all 2 solutions with explanations
Approach 1Two passes
The idea

Count the length L. Then walk L − n steps from the dummy to the node just before the one to delete.

JavaScript
function removeNthFromEnd(head, n) {  let len = 0;  for (let c = head; c !== null; c = c.next) len++;  const dummy = new ListNode(0, head);  let prev = dummy;  for (let i = 0; i < len - n; i++) prev = prev.next;  prev.next = prev.next.next;  return dummy.next;}console.log(toArray(removeNthFromEnd(fromArray([1, 2, 3, 4, 5]), 2))); // [1, 2, 3, 5]console.log(toArray(removeNthFromEnd(fromArray([1, 2]), 2)));          // [2]
How it works

O(n) time, O(1) space, but you walk the list twice.

Approach 2One pass with a gap
The idea

Move fast n steps ahead. Then move both pointers until fast is on the last node.

JavaScript
function removeNthFromEnd(head, n) {  const dummy = new ListNode(0, head);  let fast = dummy, slow = dummy;  for (let i = 0; i < n; i++) fast = fast.next;  while (fast.next !== null) { fast = fast.next; slow = slow.next; }  slow.next = slow.next.next;  return dummy.next;}console.log(toArray(removeNthFromEnd(fromArray([1, 2, 3, 4, 5]), 2))); // [1, 2, 3, 5]console.log(toArray(removeNthFromEnd(fromArray([1]), 1)));             // []
How it works

Same cost, but you walk the list only once. The dummy makes deleting the head work like any other case.

Which approach should you use?

Both are fine. The one-pass version is the answer interviewers expect. (LeetCode 19.)

Q4Intersection of two linked listsEasy

Return the node where two singly linked lists start to share nodes. If they share none, return null.

Example 1
Input: A = 1→2→8→9, B = 5→8→9 (8 is the same node)
Output: node 8
Explanation: Both lists share the tail 8→9.
Example 2
Input: A = 1, B = 2 (separate)
Output: null
Explanation: No shared node.
Stuck? Open one hint at a time
Hint 1
"Shared" means the same node object, not just the same value.
Hint 2
If both lists had the same length, you could walk them together. How can you make them the same length?
Show all 2 solutions with explanations
Approach 1Set of nodes from A
The idea

A Set is a collection that keeps each item once and can check quickly whether an item is inside. Put every node of A in a Set. Then walk B and return the first node that is in the Set.

JavaScript
function getIntersectionNode(a, b) {  const seen = new Set();  for (let c = a; c !== null; c = c.next) seen.add(c);  for (let c = b; c !== null; c = c.next) if (seen.has(c)) return c;  return null;}const shared = fromArray([8, 9]);const x = new ListNode(1, new ListNode(2, shared));const y = new ListNode(5, shared);console.log(getIntersectionNode(x, y).val); // 8
How it works

O(m + n) time, O(m) space.

Approach 2Switch lists at the end
The idea

Walk p along A and then B. Walk q along B and then A. Both walk m + n nodes, so they reach the shared node together (or both reach null).

JavaScript
function getIntersectionNode(a, b) {  let p = a, q = b;  while (p !== q) {    p = p === null ? b : p.next;    q = q === null ? a : q.next;  }  return p;}const shared = fromArray([8, 9]);const x = new ListNode(1, new ListNode(2, shared));const y = new ListNode(5, shared);console.log(getIntersectionNode(x, y).val);                       // 8console.log(getIntersectionNode(fromArray([1]), fromArray([2]))); // null
How it works

O(m + n) time, O(1) space. The difference in length cancels out. Each pointer walks the other list's extra length on its second trip.

Which approach should you use?

The switching trick is the best answer. The Set version is a safe first answer. (LeetCode 160.)

Q5Add two numbersMedium

Each list is a whole number that is not negative. It has one digit per node, with the ones digit first. Return their sum as a list in the same form.

Example 1
Input: [2, 4, 3] + [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807. The digits are stored in reverse order.
Example 2
Input: [9, 9] + [1]
Output: [0, 0, 1]
Explanation: 99 + 1 = 100. The last carry needs a new node.
Stuck? Open one hint at a time
Hint 1
The digits are stored with the ones digit first. That is the same order you use when you add by hand.
Hint 2
Keep looping while either list still has a node, or while there is a carry left.
Show all 2 solutions with explanations
Approach 1Digit by digit with a carry
The idea

At each position, add both digits (use 0 if a list has no digit left) and the carry. Store sum % 10 (the last digit of the sum). The new carry is floor(sum / 10) (the sum divided by 10, rounded down).

JavaScript
function addTwoNumbers(a, b) {  const dummy = new ListNode(0);  let tail = dummy, carry = 0;  while (a !== null || b !== null || carry > 0) {    const sum = (a ? a.val : 0) + (b ? b.val : 0) + carry;    tail.next = new ListNode(sum % 10);    carry = Math.floor(sum / 10);    tail = tail.next;    if (a) a = a.next;    if (b) b = b.next;  }  return dummy.next;}console.log(toArray(addTwoNumbers(fromArray([2, 4, 3]), fromArray([5, 6, 4])))); // [7, 0, 8]console.log(toArray(addTwoNumbers(fromArray([9, 9]), fromArray([1]))));          // [0, 0, 1]
How it works

O(max(m, n)) time (the length of the longer list). It never turns the list into a number. So it works for lists much longer than the 15 or so digits that a JavaScript number can hold exactly.

Approach 2Convert to BigInt
The idea

Read each list into a BigInt (a JavaScript type for very large whole numbers). Add them, then split the result back into a list. It is easy to write, but it skips the point of the question.

JavaScript
function toBig(head) {  let digits = "";  for (let c = head; c !== null; c = c.next) digits = c.val + digits;  return BigInt(digits);}function addTwoNumbers(a, b) {  const total = (toBig(a) + toBig(b)).toString();  const dummy = new ListNode(0);  let tail = dummy;  for (let i = total.length - 1; i >= 0; i--) { tail.next = new ListNode(Number(total[i])); tail = tail.next; }  return dummy.next;}console.log(toArray(addTwoNumbers(fromArray([2, 4, 3]), fromArray([5, 6, 4])))); // [7, 0, 8]
How it works

It gives the right answer, but interviewers expect the carry loop, and this version builds large strings. Use it only to double-check your answer.

Which approach should you use?

Use the carry loop. (LeetCode 2.)

Q6Sort listMedium

Sort a linked list from smallest to largest in O(n log n) time.

Example 1
Input: [4, 2, 1, 3]
Output: [1, 2, 3, 4]
Explanation: The list is sorted from smallest to largest.
Example 2
Input: [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
Explanation: Negative numbers work in the same way.
Stuck? Open one hint at a time
Hint 1
Which sort does not need random access (jumping straight to any position) or extra space for the merge step?
Hint 2
Split the list with slow and fast pointers. Then cut the link between the two halves.
Show all 2 solutions with explanations
Approach 1Copy to an array, sort, copy back
The idea

Read the values, sort them with sort((x, y) => x - y), and write them back into the nodes.

JavaScript
function sortList(head) {  const vals = [];  for (let c = head; c !== null; c = c.next) vals.push(c.val);  vals.sort((x, y) => x - y);  let i = 0;  for (let c = head; c !== null; c = c.next) c.val = vals[i++];  return head;}console.log(toArray(sortList(fromArray([4, 2, 1, 3])))); // [1, 2, 3, 4]
How it works

O(n log n) time, O(n) space. It is fine in real code, but it does not show that you can work with lists.

Approach 2Merge sort on the list
The idea

Split the list in the middle. Sort each half with recursion (the function calls itself). Then merge the two sorted halves.

JavaScript
function merge(a, b) {  const dummy = new ListNode(0);  let tail = dummy;  while (a !== null && b !== null) {    if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }    tail = tail.next;  }  tail.next = a !== null ? a : b;  return dummy.next;}function sortList(head) {  if (head === null || head.next === null) return head;  let slow = head, fast = head.next;  while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; }  const second = slow.next;  slow.next = null;  return merge(sortList(head), sortList(second));}console.log(toArray(sortList(fromArray([-1, 5, 3, 4, 0])))); // [-1, 0, 3, 4, 5]
How it works

O(n log n) time. The recursion goes O(log n) levels deep. A bottom-up version (it merges groups of size 1, 2, 4, and so on, with no recursion) needs only O(1) extra space.

Which approach should you use?

Use merge sort. (LeetCode 148.)

Q7Reorder listMedium

Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → … by changing the links of the nodes in place (no new nodes).

Example 1
Input: [1, 2, 3, 4]
Output: [1, 4, 2, 3]
Explanation: Take one from the front, then one from the back, and so on: 1, 4, 2, 3.
Example 2
Input: [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]
Explanation: Take 1, 5, 2, 4, and then the middle node 3 is left.
Stuck? Open one hint at a time
Hint 1
This question uses three earlier ideas one after another. Find the middle, reverse the second half, and then merge by taking one node from each half in turn.
Show all 2 solutions with explanations
Approach 1Array of nodes with two pointers
The idea

Store the nodes in an array. Then link them again, working from both ends towards the middle.

JavaScript
function reorderList(head) {  const nodes = [];  for (let c = head; c !== null; c = c.next) nodes.push(c);  let i = 0, j = nodes.length - 1;  while (i < j) {    nodes[i].next = nodes[j];    i++;    if (i === j) break;    nodes[j].next = nodes[i];    j--;  }  nodes[i].next = null;}const h = fromArray([1, 2, 3, 4, 5]);reorderList(h);console.log(toArray(h)); // [1, 5, 2, 4, 3]
How it works

O(n) time, O(n) space. The last line is the important one. Without it, the final node still points at its old neighbour, and the list becomes a cycle.

Approach 2Middle + reverse + interleave
The idea
  1. Find the end of the first half and cut the list at that point.
  2. Reverse the second half.
  3. Take one node from each half in turn (interleave them).
JavaScript
function reorderList(head) {  if (head === null || head.next === null) return;  let slow = head, fast = head;  while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; }  let prev = null, cur = slow.next;  slow.next = null;  while (cur !== null) { const next = cur.next; cur.next = prev; prev = cur; cur = next; }  let a = head, b = prev;  while (b !== null) {    const an = a.next, bn = b.next;    a.next = b;    b.next = an;    a = an;    b = bn;  }}const h = fromArray([1, 2, 3, 4]);reorderList(h);console.log(toArray(h)); // [1, 4, 2, 3]const g = fromArray([1, 2, 3, 4, 5]);reorderList(g);console.log(toArray(g)); // [1, 5, 2, 4, 3]
How it works

O(n) time, O(1) space. The first half is never shorter than the second. So when the length is odd, the list ends with its middle node after interleaving.

Which approach should you use?

The array version is a good first answer. The three-step version is the follow-up. (LeetCode 143.)

Make it stick

Make it stick — close this page, then
  1. Write the merge loop with a dummy head. Explain the last line (tail.next = a || b).
  2. Describe the two phases for finding where a cycle starts. Say what the second phase does.
  3. Explain how a gap of n nodes finds the n-th node from the end in one pass.
  4. Explain why the intersection trick makes both pointers walk the same distance.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

Lesson 38 leaves lists and brings a new structure: the stack. A stack is last in, first out, like a pile of plates. You use it to match brackets, to build a stack that knows its minimum, and to work out expressions.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series