Reorder Linked List in DSA Javascript

Mental Model

We rearrange the list so nodes alternate from start and end towards the center.

Analogy: Imagine lining up people from two ends of a line, taking one from the front, then one from the back, repeating until all are in a new order.

1 -> 2 -> 3 -> 4 -> 5 -> null
↓                 ↑
front             end

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> null

Goal: Rearrange to 1 -> 5 -> 2 -> 4 -> 3 -> null

Step 1: Find middle node using slow and fast pointers

1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑slow
                ↑fast

Why: We need to split the list into two halves at the middle

Step 2: Split list into two halves: first half 1->2->3, second half 4->5

First half: 1 -> 2 -> 3 -> null
Second half: 4 -> 5 -> null

Why: Separating halves helps to reorder by merging from front and back

Step 3: Reverse second half to get 5 -> 4 -> null

Second half reversed: 5 -> 4 -> null

Why: Reversing second half allows easy alternating merge

Step 4: Merge first half and reversed second half alternately

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

Why: Alternating nodes from front and back achieves the reorder

Result:

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

Annotated Code

DSA Javascript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reorderList(head) {
  if (!head || !head.next) return;

  // Find middle of list
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next; // advance slow by 1
    fast = fast.next.next; // advance fast by 2
  }

  // Split and reverse second half
  let second = slow.next;
  slow.next = null; // break list
  second = reverseList(second);

  // Merge two halves
  let first = head;
  while (second) {
    let tmp1 = first.next;
    let tmp2 = second.next;

    first.next = second; // link first node to second
    second.next = tmp1; // link second node to next of first

    first = tmp1; // move first pointer
    second = tmp2; // move second pointer
  }
}

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    let nextTemp = curr.next;
    curr.next = prev; // reverse pointer
    prev = curr; // move prev forward
    curr = nextTemp; // move curr forward
  }
  return prev;
}

// Driver code
function printList(head) {
  let curr = head;
  let result = '';
  while (curr) {
    result += curr.val + ' -> ';
    curr = curr.next;
  }
  result += 'null';
  console.log(result);
}

// Create list 1 -> 2 -> 3 -> 4 -> 5 -> null
const head = new ListNode(1,
  new ListNode(2,
    new ListNode(3,
      new ListNode(4,
        new ListNode(5)))));

console.log('Original list:');
printList(head);
reorderList(head);
console.log('Reordered list:');
printList(head);

while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }

Find middle node by moving slow 1 step and fast 2 steps

slow.next = null;

Split list into two halves by breaking link at middle

second = reverseList(second);

Reverse second half to prepare for merging

while (second) { first.next = second; second.next = tmp1; first = tmp1; second = tmp2; }

Merge nodes alternately from first and reversed second halves

curr.next = prev; prev = curr; curr = nextTemp;

Reverse pointers in second half

Output

Original list:

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

Reordered list:

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

Complexity Analysis

Time: O(n) because we traverse the list multiple times but each pass is linear

Space: O(1) because we reorder in place without extra data structures

vs Alternative: Naive approach might use extra arrays to reorder, costing O(n) space; this method is more efficient with O(1) space

Edge Cases

Empty list

Function returns immediately without changes

DSA Javascript

if (!head || !head.next) return;

Single node list

No reorder needed, list remains same

DSA Javascript

if (!head || !head.next) return;

Two nodes list

Reorder does nothing visible, list remains same

DSA Javascript

while (fast.next && fast.next.next) { ... } prevents splitting beyond middle

When to Use This Pattern

When asked to reorder a linked list alternating from front and back, use the reorder list pattern by splitting, reversing second half, and merging.

Common Mistakes

Mistake: Not breaking the list at the middle, causing cycles or incorrect merges
Fix: Set slow.next = null to split the list cleanly

Mistake: Merging without reversing second half, resulting in wrong order
Fix: Reverse the second half before merging

Mistake: Not handling edge cases like empty or single node lists
Fix: Add guard clause to return early if list too short

Summary

Rearranges a linked list so nodes alternate from start and end towards the center.

Use when you need to reorder a list in a specific alternating pattern without extra space.

Split the list, reverse the second half, then merge nodes alternately to reorder.

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