Reorder Linked List in DSA Javascript - Execution Trace

Concept Flow - Reorder Linked List

Start at head

↓

Find middle node

→Split list into two halves

↓

Reverse second half

↓

Merge two halves alternately

↓

Reordered list complete

We find the middle of the list, reverse the second half, then merge nodes from both halves alternately to reorder the list.

Execution Sample

DSA Javascript

function reorderList(head) {
  if (!head || !head.next) return;
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let second = reverseList(slow.next);
  slow.next = null;
  let first = head;
  while (second) {
    let tmp1 = first.next;
    let tmp2 = second.next;
    first.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    let nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }
  return prev;
}

This code reorders a linked list by splitting, reversing the second half, and merging alternately.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with list	1 -> 2 -> 3 -> 4 -> 5 -> null	head points to 1	1 -> 2 -> 3 -> 4 -> 5 -> null
2	Find middle node using slow and fast pointers	1 -> 2 -> 3 -> 4 -> 5 -> null	slow at 3, fast at 5	1 -> 2 -> (3) -> 4 -> 5 -> null
3	Split list into two halves at middle	First half: 1 -> 2 -> 3 -> null Second half: 4 -> 5 -> null	slow.next set to null	1 -> 2 -> 3 -> null 4 -> 5 -> null
4	Reverse second half	4 -> 5 -> null	4.next set to null, 5.next set to 4	5 -> 4 -> null
5	Merge two halves alternately	First half: 1 -> 2 -> 3 -> null Second half reversed: 5 -> 4 -> null	1.next = 5, 5.next = 2 2.next = 4, 4.next = 3	1 -> 5 -> 2 -> 4 -> 3 -> null
6	Reordering complete	1 -> 5 -> 2 -> 4 -> 3 -> null	No pointer changes	1 -> 5 -> 2 -> 4 -> 3 -> null

💡 All nodes merged alternately, second half exhausted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
head	1	1	1	1	1	1
slow	1	3	3	3	3	3
fast	1	5	5	5	5	5
second (second half head)	null	null	4	5	4	null
first (first half head)	1	1	1	1	1	1

Key Moments - 3 Insights

Why do we set slow.next = null after finding the middle?

Setting slow.next = null splits the list into two separate halves, preventing cycles during merging. See execution_table step 3 where the list is split.

Why do we reverse the second half before merging?

Reversing the second half allows us to merge nodes alternately from start and end. Without reversing, the order would not match the required pattern. See execution_table step 4 for reversal.

How does the merging process alternate nodes from both halves?

We take one node from the first half, then one from the reversed second half, updating pointers each time. This is shown in execution_table step 5 with pointer changes.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, where is the slow pointer located?

A At node 3

B At node 4

C At node 2

D At node 5

💡 Hint

Check the 'Pointer Changes' column in step 2 of execution_table.

At which step does the second half get reversed?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look for 'Reverse second half' in the 'Operation' column.

If we do not set slow.next = null, what will happen during merging?

A The list will merge correctly

B The list will become cyclic

C The second half will be empty

D The first half will be reversed

💡 Hint

Refer to key_moments about splitting the list and pointer changes at step 3.

Concept Snapshot

Reorder Linked List:
1. Find middle with slow & fast pointers.
2. Split list into two halves.
3. Reverse second half.
4. Merge halves alternately.
Result: nodes reordered as first, last, second, second-last, ...

Full Transcript

This visualization shows how to reorder a linked list by first finding the middle node using slow and fast pointers. Then the list is split into two halves by setting slow.next to null. The second half is reversed to prepare for merging. Finally, nodes from the first half and reversed second half are merged alternately to form the reordered list. The execution table tracks each step with pointer changes and the visual state of the list. Key moments clarify why splitting and reversing are necessary. The quiz tests understanding of pointer positions and effects of operations.

Practice

1. What is the main goal of the Reorder Linked List problem?

easy

A. Rearrange the list so nodes alternate from start and end towards the center

B. Sort the linked list in ascending order

C. Reverse the entire linked list

D. Remove duplicate nodes from the linked list

Solution

1. Step 1: Understand the problem goal

   The problem asks to reorder nodes so the first node is followed by the last node, then second node, then second last, and so on.

2. Step 2: Differentiate from other operations

   This is not sorting or reversing the whole list, but alternating nodes from front and back.

3. Final Answer:

   Rearrange the list so nodes alternate from start and end towards the center -> Option A

4. Quick Check:

   Reorder Linked List = Alternate front and back nodes [OK]

Hint: Think of weaving nodes from front and back alternately [OK]

Common Mistakes:

• Confusing reorder with sorting
• Trying to reverse the entire list only
• Ignoring the alternating pattern

2. Which of the following code snippets correctly finds the middle node of a singly linked list in JavaScript?

easy

A. let slow = head; let fast = head.next; while(fast) { slow = slow.next; fast = fast.next; }

B. let slow = head; while(slow.next) { slow = slow.next.next; }

C. let fast = head; while(fast.next) { fast = fast.next.next; }

D. let slow = head, fast = head; while(fast && fast.next) { slow = slow.next; fast = fast.next.next; }

Solution

1. Step 1: Use two pointers to find middle

   Initialize two pointers: slow moves one step, fast moves two steps until fast reaches end.

2. Step 2: Check each option

   let slow = head, fast = head; while(fast && fast.next) { slow = slow.next; fast = fast.next.next; } correctly moves slow by one and fast by two steps in the loop condition.

3. Final Answer:

   let slow = head, fast = head; while(fast && fast.next) { slow = slow.next; fast = fast.next.next; } -> Option D

4. Quick Check:

   Fast moves twice, slow moves once to find middle [OK]

Hint: Use slow and fast pointers; fast moves twice as fast [OK]

Common Mistakes:

• Moving slow pointer incorrectly
• Not checking fast and fast.next in loop condition
• Starting fast pointer incorrectly

3. Given the linked list 1 -> 2 -> 3 -> 4 -> null, what will be the reordered list after applying the reorder algorithm?

medium

A. 1 -> 2 -> 3 -> 4 -> null

B. 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 4 -> 2 -> 3 -> null

D. 1 -> 3 -> 2 -> 4 -> null

Solution

1. Step 1: Identify the reorder pattern

   The reorder pattern is first node, last node, second node, second last node, and so on.

2. Step 2: Apply pattern to list 1->2->3->4

   Start with 1, then 4, then 2, then 3, resulting in 1 -> 4 -> 2 -> 3 -> null.

3. Final Answer:

   1 -> 4 -> 2 -> 3 -> null -> Option C

4. Quick Check:

   Alternate front and back nodes = 1->4->2->3 [OK]

Hint: Alternate nodes from front and back to reorder [OK]

Common Mistakes:

• Reversing the entire list instead
• Not alternating nodes correctly
• Leaving list unchanged

4. Consider this buggy code snippet for reordering a linked list:

function reorderList(head) {
  if (!head) return;
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let second = slow.next;
  slow.next = null;
  second = reverseList(second);
  let first = head;
  while (second) {
    let temp1 = first.next;
    let temp2 = second.next;
    first.next = second;
    second.next = temp1;
    first = temp1;
    second = temp2;
  }
}

function reverseList(head) {
  let prev = null;
  while (head) {
    let next = head.next;
    head.next = prev;
    prev = head;
    head = next;
  }
  return prev;
}

What is the bug in this code?

medium

A. The merging loop does not handle the case when first becomes null

B. The loop condition for finding middle is incorrect and may skip nodes

C. The reverseList function does not return the reversed list

D. The slow pointer is not moved correctly to split the list

Solution

1. Step 1: Analyze the merging loop

   The merging loop assumes first is never null, but if first becomes null before second, it causes errors.

2. Step 2: Identify missing null check

   There is no check if first is null before accessing first.next, which can cause runtime errors.

3. Final Answer:

   The merging loop does not handle the case when first becomes null -> Option A

4. Quick Check:

   Merging loop must check first != null to avoid errors [OK]

Hint: Check null before accessing next pointers in merge loop [OK]

Common Mistakes:

• Ignoring null checks in merging loop
• Thinking reverseList is faulty
• Misreading middle finding loop condition

5. You have a linked list with nodes: 1 -> 2 -> 3 -> 4 -> 5 -> null. After reordering, what will be the final linked list?

hard

A. 5 -> 4 -> 3 -> 2 -> 1 -> null

B. 1 -> 5 -> 2 -> 4 -> 3 -> null

C. 1 -> 3 -> 5 -> 2 -> 4 -> null

D. 1 -> 2 -> 3 -> 4 -> 5 -> null

Solution

1. Step 1: Understand reorder pattern for odd length list

   For odd length, reorder as first node, last node, second node, second last node, then middle node.

2. Step 2: Apply to list 1->2->3->4->5

   Sequence: 1 (first), 5 (last), 2 (second), 4 (second last), 3 (middle).

3. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> null -> Option B

4. Quick Check:

   Alternate front and back nodes with middle last [OK]

Hint: Alternate front and back nodes, middle stays last if odd length [OK]

Common Mistakes:

• Reversing entire list
• Not handling odd length middle node correctly
• Leaving list unchanged