Reorder Linked List in DSA Javascript - Deep Dive

Overview - Reorder Linked List

What is it?

Reorder Linked List is a process where we change the order of nodes in a linked list so that the first node is followed by the last node, then the second node, then the second last node, and so on. This rearrangement creates a new pattern without adding or removing nodes. It helps in solving problems where we want to mix the start and end parts of a list in a specific way.

Why it matters

Without reordering, linked lists keep their original order, which might not be useful for certain tasks like alternating data display or merging two ends. Reordering helps in optimizing data access patterns and can be used in algorithms that require mixing elements from both ends. Without this concept, some problems would be harder or less efficient to solve.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After mastering reorder linked list, you can explore advanced linked list manipulations like cycle detection, merging sorted lists, or doubly linked lists.

Mental Model

Core Idea

Reorder Linked List means weaving nodes from the start and end of the list alternately to create a new sequence without changing node values or adding new nodes.

Think of it like...

Imagine a line of people waiting to enter a room. Instead of letting them enter in the original order, you let the first person in, then the last person, then the second person, then the second last person, and so on, mixing the front and back of the line.

Original List: 1 -> 2 -> 3 -> 4 -> 5 -> null
Reordered List: 1 -> 5 -> 2 -> 4 -> 3 -> null

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Basics

Concept: Learn what a linked list is and how nodes connect to each other.

A linked list is a chain of nodes where each node has a value and a pointer to the next node. The last node points to null, marking the end. For example, 1 -> 2 -> 3 -> null means node 1 points to node 2, node 2 points to node 3, and node 3 points to null.

Result

You can follow the chain from the first node to the last by following the pointers.

Understanding how nodes link is essential because reordering changes these links without changing node values.

2

Foundation

Traversing a Linked List

Concept: Learn how to visit each node in order from start to end.

Start at the head node. While the current node is not null, read its value and move to the next node. This lets you see all values in order.

Result

You can print or process all nodes in the list one by one.

Traversal is the foundation for any linked list operation, including reordering.

3

Intermediate

Finding the Middle Node

🤔Before reading on: do you think you can find the middle node by counting nodes first or by moving two pointers at different speeds? Commit to your answer.

Concept: Use two pointers moving at different speeds to find the middle node efficiently.

Use a slow pointer that moves one step at a time and a fast pointer that moves two steps. When the fast pointer reaches the end, the slow pointer is at the middle.

Result

You get the middle node without counting all nodes first.

Knowing the middle helps split the list into two parts, which is key for reordering.

4

Intermediate

Reversing the Second Half

🤔Before reading on: do you think reversing the second half means changing node values or changing pointers? Commit to your answer.

Concept: Reverse the links between nodes in the second half to prepare for weaving.

Starting from the middle node's next, reverse the next pointers so the last node points backward. This changes the order of nodes in the second half.

Result

The second half of the list is reversed, e.g., 4 -> 5 becomes 5 -> 4.

Reversing the second half allows easy alternating merge with the first half.

5

Intermediate

Merging Two Halves Alternately

🤔Before reading on: do you think merging alternately means appending one half fully then the other, or weaving nodes one by one? Commit to your answer.

Concept: Weave nodes from the first half and reversed second half one by one to reorder.

Take one node from the first half, then one from the reversed second half, link them alternately until all nodes are merged.

Result

The list is reordered as first node, last node, second node, second last node, etc.

Alternating merge creates the final reordered pattern without extra space.

6

Advanced

Complete Reorder Algorithm in JavaScript

🤔Before reading on: do you think the reorder can be done in-place without extra arrays or lists? Commit to your answer.

Concept: Combine finding middle, reversing second half, and merging to reorder in-place.

function reorderList(head) { if (!head || !head.next) return; // Find middle let slow = head, fast = head; while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; } // Reverse second half let prev = null, curr = slow.next; while (curr) { let nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } slow.next = null; // Split list // Merge two halves let first = head, second = prev; while (second) { let temp1 = first.next; let temp2 = second.next; first.next = second; second.next = temp1; first = temp1; second = temp2; } } // Example usage: // List: 1 -> 2 -> 3 -> 4 -> 5 -> null // After reorderList(head): 1 -> 5 -> 2 -> 4 -> 3 -> null

Result

The linked list nodes are reordered in-place to the pattern described.

Knowing how to combine these steps lets you reorder efficiently without extra memory.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think the algorithm works the same for even and odd length lists? Commit to your answer.

Concept: Understand how the algorithm adapts to lists with even or odd numbers of nodes and its time and space complexity.

For even length, the middle is just before the second half; for odd length, the middle node stays in place. The algorithm runs in O(n) time and O(1) space because it only traverses the list a few times and changes pointers in place.

Result

The reorder works correctly for all list lengths and is efficient.

Recognizing these details ensures robustness and optimal performance in real applications.

Under the Hood

The algorithm works by first finding the middle node using two pointers moving at different speeds. Then it reverses the second half of the list by changing the next pointers of nodes to point backward. Finally, it merges the two halves by alternating nodes from the first half and the reversed second half, adjusting pointers to weave them together. This all happens by changing pointers, not node values, so the list is reordered in place without extra memory.

Why designed this way?

This approach was designed to reorder the list efficiently without using extra space like arrays or stacks. Using two pointers to find the middle is a classic technique to avoid counting nodes first. Reversing the second half prepares it for easy merging. The in-place merge avoids extra memory and keeps the algorithm linear in time, which is important for large lists.

Head
 ↓
┌───┐    ┌───┐    ┌───┐    ┌───┐    ┌───┐
│ 1 │ -> │ 2 │ -> │ 3 │ -> │ 4 │ -> │ 5 │ -> null
└───┘    └───┘    └───┘    └───┘    └───┘

Step 1: Find middle (node 3)

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

Step 2: Reverse second half
Second half reversed: 5 -> 4 -> null

Step 3: Merge alternately
1 -> 5 -> 2 -> 4 -> 3 -> null

Myth Busters - 4 Common Misconceptions

Quick: Do you think reordering changes the values inside nodes? Commit to yes or no.

Common Belief: Reordering means changing the values inside the nodes to rearrange the list.

Reality: Reordering changes the pointers between nodes, not the values inside them.

Why it matters: Changing values instead of pointers can cause data corruption or lose the original node structure, which is not the goal.

Quick: Do you think you need extra arrays or lists to reorder a linked list? Commit to yes or no.

Common Belief: You must copy nodes into an array or another list to reorder them.

Reality: The reorder can be done in-place by changing pointers without extra memory.

Why it matters: Using extra memory wastes space and reduces efficiency, especially for large lists.

Quick: Do you think the algorithm works the same for even and odd length lists without any adjustment? Commit to yes or no.

Common Belief: The reorder algorithm treats even and odd length lists exactly the same way.

Reality: The middle node handling differs slightly; for odd length, the middle node stays at the end of the reordered list.

Why it matters: Ignoring this can cause incorrect pointer assignments and break the list.

Quick: Do you think reversing the second half means swapping node values? Commit to yes or no.

Common Belief: Reversing the second half means swapping the values inside nodes.

Reality: Reversing means changing the next pointers to reverse the node order, not swapping values.

Why it matters: Swapping values can be inefficient and lose node identity important in some applications.

Expert Zone

1

The slow and fast pointer technique not only finds the middle but also ensures the first half is always one node longer for odd length lists, which simplifies merging.

2

Reversing the second half in place avoids the need for recursion or extra stacks, which can cause stack overflow on large lists.

3

During merging, careful pointer updates prevent cycles or lost nodes, a subtlety often missed leading to infinite loops or broken lists.

When NOT to use

Avoid this approach if the list is doubly linked and you want to preserve backward links without extra updates, or if you need to maintain stable node order for equal elements. In such cases, consider using auxiliary data structures or different algorithms like stable merges.

Production Patterns

This reorder pattern is used in problems like rearranging playlists, alternating data streams, or preparing data for zigzag traversal. It is also a common interview question to test pointer manipulation skills and in-place algorithm design.

Connections

Two Pointer Technique

Reorder Linked List uses the two pointer technique to find the middle node efficiently.

Understanding two pointers helps grasp how to split lists quickly without counting nodes.

In-place Array Reversal

Reversing the second half of the linked list is conceptually similar to reversing an array segment in place.

Knowing array reversal helps understand pointer reversal in linked lists.

Weaving in Textile Manufacturing

The alternating merge step is like weaving threads from two ends to create a pattern.

Recognizing weaving patterns in textiles helps appreciate the alternating merge process in linked lists.

Common Pitfalls

#1 Breaking the list without reconnecting halves properly.

Wrong approach:

slow.next = null; // but forget to merge second half
// Result: list ends prematurely, losing nodes.

Correct approach:

slow.next = null; // split list
// then merge first half and reversed second half carefully.

Root cause:

Forgetting to merge after splitting causes loss of nodes.

#2 Incorrect pointer updates during merge causing cycles.

Wrong approach:

first.next = second;
second.next = first; // wrong, creates cycle

Correct approach:

first.next = second;
second.next = temp1; // temp1 is next node in first half

Root cause:

Not saving next pointers before re-linking causes cycles.

#3 Not handling empty or single-node lists.

Wrong approach:

function reorderList(head) {
// no check for null or single node
// proceeds and causes errors
}

Correct approach:

function reorderList(head) {
if (!head || !head.next) return;
// safe to proceed
}

Root cause:

Ignoring edge cases leads to runtime errors.

Key Takeaways

Reorder Linked List rearranges nodes by weaving from start and end alternately without changing node values.

The process uses three main steps: find middle, reverse second half, and merge alternately.

This algorithm works in-place with O(n) time and O(1) space, making it efficient for large lists.

Understanding pointer manipulation and edge cases is crucial to avoid bugs like cycles or lost nodes.

Mastering this technique builds strong skills in linked list manipulation and in-place algorithms.

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