Reorder Linked List in DSA Typescript

Mental Model

We rearrange the list so nodes alternate from start and end, meeting in the middle.

Analogy: Imagine lining up people from two ends of a line and having them walk towards the center, taking turns stepping forward.

1 -> 2 -> 3 -> 4 -> 5 -> null
↑start pointer

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 at 3, fast at 5

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 allows reversing the second half

Step 3: Reverse second half

Second half reversed: 5 -> 4 -> null

Why: Reversing lets us alternate nodes from front and back

Step 4: Merge nodes alternately from first half and reversed second half

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

Why: Alternating nodes achieves the reorder pattern

Result:

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

Annotated Code

DSA Typescript

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;

  // Find middle of list
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  // Split the list into two halves
  let firstHalfEnd = head;
  while (firstHalfEnd.next !== slow) {
    firstHalfEnd = firstHalfEnd.next!;
  }
  firstHalfEnd.next = null;

  // Reverse second half
  let prev: ListNode | null = null;
  let curr: ListNode | null = slow;
  while (curr) {
    const nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }

  // Merge two halves
  let first: ListNode | null = head;
  let second: ListNode | null = prev;
  while (second) {
    const tmp1 = first!.next;
    const tmp2 = second.next;
    first!.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}

// Driver code to test
function printList(head: ListNode | null): string {
  let curr = head;
  let result = '';
  while (curr) {
    result += curr.val + ' -> ';
    curr = curr.next;
  }
  return result + 'null';
}

// Create list 1 -> 2 -> 3 -> 4 -> 5 -> null
const node5 = new ListNode(5);
const node4 = new ListNode(4, node5);
const node3 = new ListNode(3, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);

console.log('Before reorder: ' + printList(node1));
reorderList(node1);
console.log('After reorder: ' + printList(node1));

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

advance slow and fast pointers to find middle node

while (curr) { const nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; }

reverse second half of the list

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

merge nodes alternately from first and reversed second half

Output

Before reorder: 1 -> 2 -> 3 -> 4 -> 5 -> null

After reorder: 1 -> 5 -> 2 -> 4 -> 3 -> null

Complexity Analysis

Time: O(n) because we traverse the list multiple times but each node is visited a constant number of times

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

vs Alternative: Compared to creating a new list or array to reorder, this approach uses no extra space and is more efficient

Edge Cases

empty list

function returns immediately without changes

DSA Typescript

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

single node list

function returns immediately without changes

DSA Typescript

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

list with two nodes

reorder does nothing as list is already in desired order

DSA Typescript

while (fast && fast.next) { ... } handles middle correctly

When to Use This Pattern

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

Common Mistakes

Mistake: Not breaking the list into two halves before reversing second half
Fix: Use slow and fast pointers to find middle and start reversal from middle

Mistake: Merging nodes without checking for overlap causing cycles
Fix: Stop merging when first and second pointers meet or cross

Summary

Rearranges a linked list so nodes alternate from front and back 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

B. Sort the linked list in ascending order

C. Remove duplicate nodes from the list

D. Reverse the entire linked list

Solution

1. Step 1: Understand the problem statement

   The problem asks to reorder the list so that nodes come alternatively from the start and the end of the list.

2. Step 2: Differentiate from other operations

   This is not sorting, removing duplicates, or full reversal. It is a specific rearrangement pattern.

3. Final Answer:

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

4. Quick Check:

   Reorder Linked List = Alternate nodes from start and end [OK]

Hint: Remember: reorder means alternate front and back nodes [OK]

Common Mistakes:

• Confusing reorder with sorting
• Thinking reorder means full reversal
• Assuming duplicates are removed

2. Which TypeScript syntax correctly defines a singly linked list node for the reorder problem?

easy

A. function ListNode(val) { this.val = val; this.next = null; }

B. class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } }

C. interface ListNode { val: number; next: ListNode; }

D. type ListNode = { val: number; next?: ListNode }

Solution

1. Step 1: Identify correct TypeScript class syntax

   class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } } defines a class with a constructor and proper typing for next as nullable.

2. Step 2: Check other options for correctness

   function ListNode(val) { this.val = val; this.next = null; } is JavaScript style without types, C misses null for next, D uses optional but not null which is less precise.

3. Final Answer:

   class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } } -> Option B

4. Quick Check:

   Correct TypeScript class with nullable next = class ListNode { val: number; next: ListNode | null; constructor(val: number) { this.val = val; this.next = null; } } [OK]

Hint: Use class with constructor and next as nullable for linked list node [OK]

Common Mistakes:

• Omitting null for next pointer
• Using interface without nullability
• Using JavaScript function syntax without types

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

medium

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern

   The reorder pattern takes first node, then last node, then second node, then 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:

   Reorder 1-4 = 1->4->2->3 [OK]

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

Common Mistakes:

• Reversing entire list instead of reordering
• Swapping adjacent nodes incorrectly
• Mixing node order without pattern

4. Consider this TypeScript snippet for reordering a linked list:

let slow = head;
let fast = head;
while (fast && fast.next) {
  slow = slow.next;
  fast = fast.next.next;
}
// Missing step here
let second = slow.next;
slow.next = null;
// Reverse second half and merge

What is the missing step to correctly reorder the list?

medium

A. Move slow pointer back to head

B. Set slow.next = head to create a cycle

C. Skip reversing and merge directly

D. Reverse the second half starting from 'second' before merging

Solution

1. Step 1: Identify the role of slow and fast pointers

   They find the middle of the list; slow ends at middle node.

2. Step 2: Recognize the missing step

   After splitting, the second half must be reversed before merging to reorder correctly.

3. Final Answer:

   Reverse the second half starting from 'second' before merging -> Option D

4. Quick Check:

   Reverse second half before merge = Reverse the second half starting from 'second' before merging [OK]

Hint: Always reverse second half before merging in reorder [OK]

Common Mistakes:

• Not reversing second half before merge
• Creating cycles by wrong pointer assignments
• Moving slow pointer incorrectly

5. You have a linked list with nodes: 1 -> 2 -> 3 -> 4 -> 5 -> null. After reordering, what is the correct final list? Also, explain why the middle node is handled this way.

hard

A. 1 -> 5 -> 2 -> 4 -> 3 -> null; middle node stays last to maintain order

B. 5 -> 4 -> 3 -> 2 -> 1 -> null; middle node reversed with rest

C. 1 -> 3 -> 5 -> 2 -> 4 -> null; middle node moved to front

D. 1 -> 2 -> 3 -> 4 -> 5 -> null; no change for odd length

Solution

1. Step 1: Apply reorder pattern to odd length list

   Start with 1, then last 5, then 2, then 4, then middle 3 remains at end.

2. Step 2: Explain middle node handling

   For odd length, middle node stays in place after merging reversed second half to keep correct order.

3. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> null; middle node stays last to maintain order -> Option A

4. Quick Check:

   Odd length reorder keeps middle last = 1 -> 5 -> 2 -> 4 -> 3 -> null; middle node stays last to maintain order [OK]

Hint: Middle node stays last in odd-length reorder [OK]

Common Mistakes:

• Reversing entire list instead of partial
• Moving middle node incorrectly
• Assuming no reorder for odd length