Reorder Linked List in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Reordering a Linked List

What is the printed state of the linked list after running the reorder function on the list 1 -> 2 -> 3 -> 4 -> 5 -> null?

DSA Javascript

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

function printList(head) {
  let result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  return result.join(' -> ') + ' -> null';
}

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;

  // 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;
  }
}

// Setup linked list
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
reorderList(head);
console.log(printList(head));

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

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

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

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

💡 Hint

Think about splitting the list into two halves, reversing the second half, then merging alternately.

The reorderList function splits the list into two halves, reverses the second half, and then merges nodes alternately from the first and reversed second half. This results in the order 1 -> 5 -> 2 -> 4 -> 3 -> null.

🧠 Conceptual

intermediate

Understanding the Reorder List Algorithm

Which step is NOT part of the standard approach to reorder a linked list as per the common algorithm?

A Reverse the second half of the list

B Sort the entire list in ascending order

C Find the middle of the list using slow and fast pointers

D Merge the two halves by alternating nodes

💡 Hint

Reordering does not involve sorting the list.

The reorder list algorithm involves finding the middle, reversing the second half, and merging alternately. Sorting the list is not part of this process.

🔧 Debug

advanced

Identify the Error in Reorder List Implementation

What error will this code produce when trying to reorder the list 1 -> 2 -> 3 -> 4 -> null? function reorderList(head) { if (!head) return; let slow = head, fast = head.next; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } let second = slow.next; slow.next = null; let prev = null; while (second) { let temp = second.next; second.next = prev; prev = second; second = temp; } let first = head; while (prev) { let temp1 = first.next; let temp2 = prev.next; first.next = prev; prev.next = temp1; first = temp1; prev = temp2; } }

A No error, outputs reordered list correctly

B Infinite loop causing program to hang

C TypeError: Cannot read property 'next' of null

D ReferenceError: slow is not defined

💡 Hint

Check how the pointers move and if any can become null unexpectedly.

The code sets fast = head.next initially, which causes the while loop to run incorrectly for even length lists, leading to first or prev becoming null and accessing next property causing TypeError.

📝 Syntax

advanced

Syntax Error in Reorder List Code

Which option contains a syntax error that will prevent the reorder list function from running?

DSA Javascript

function reorderList(head) {
  if (!head || !head.next) 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;
  let prev = null;
  while (second) {
    let temp = second.next;
    second.next = prev;
    prev = second;
    second = temp;
  }
  let first = head;
  while (prev) {
    let temp1 = first.next;
    let temp2 = prev.next;
    first.next = prev;
    prev.next = temp1;
    first = temp1;
    prev = temp2;
  }
}

A function reorderList(head) { if (!head || !head.next) 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; let prev = null; while (second) { let temp = second.next; second.next = prev; prev = second; second = temp; } let first = head; while (prev) { let temp1 = first.next; let temp2 = prev.next; first.next = prev; prev.next = temp1; first = temp1; prev = temp2; }

B } } ;2pmet = verp ;1pmet = tsrif ;1pmet = txen.verp ;verp = txen.tsrif ;txen.verp = 2pmet tel ;txen.tsrif = 1pmet tel { )verp( elihw ;daeh = tsrif tel } ;pmet = dnoces ;dnoces = verp ;verp = txen.dnoces ;txen.dnoces = pmet tel { )dnoces( elihw ;llun = verp tel ;llun = txen.wols ;txen.wols = dnoces tel } ;txen.txen.tsaf = tsaf ;txen.wols = wols { )txen.txen.tsaf && txen.tsaf( elihw ;daeh = tsaf ,daeh = wols tel ;nruter )txen.daeh! || daeh!( fi { )daeh(tsiLredroer noitcnuf

C unction reorderList(head) { if (!head || !head.next) 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; let prev = null; while (second) { let temp = second.next; second.next = prev; prev = second; second = temp; } let first = head; while (prev) { let temp1 = first.next; let temp2 = prev.next; first.next = prev; prev.next = temp1; first = temp1; prev = temp2; } }

D function reorderList(head) { if (!head || !head.next) 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; let prev = null; while (second) { let temp = second.next; second.next = prev; prev = second; second = temp; } let first = head; while (prev) { let temp1 = first.next; let temp2 = prev.next; first.next = prev; prev.next = temp1; first = temp1; prev = temp2; } }

💡 Hint

Look for missing closing braces or parentheses.

Option A is missing the closing brace for the function, causing a syntax error.

🚀 Application

expert

Reorder List with Even Number of Nodes

Given the linked list 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null, what is the state of the list after applying the reorderList function?

DSA Javascript

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

function reorderList(head) {
  if (!head || !head.next) 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;
  let prev = null;
  while (second) {
    let temp = second.next;
    second.next = prev;
    prev = second;
    second = temp;
  }
  let first = head;
  while (prev) {
    let temp1 = first.next;
    let temp2 = prev.next;
    first.next = prev;
    prev.next = temp1;
    first = temp1;
    prev = temp2;
  }
}

// Setup linked list
let head = new ListNode(10, new ListNode(20, new ListNode(30, new ListNode(40, new ListNode(50, new ListNode(60))))));
reorderList(head);

function printList(head) {
  let result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  return result.join(' -> ') + ' -> null';
}

console.log(printList(head));

A 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null

B 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null

C 60 -> 50 -> 40 -> 30 -> 20 -> 10 -> null

D 10 -> 50 -> 20 -> 40 -> 30 -> 60 -> null

💡 Hint

Remember to split, reverse second half, then merge alternately.

The reorderList function splits the list at the middle (after 30), reverses the second half (60 -> 50 -> 40), then merges alternately with the first half (10 -> 20 -> 30), resulting in 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null.

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