Reorder Linked List in DSA Javascript - Build from Scratch

Reorder Linked List

📖 Scenario: You are working on a messaging app that displays chat messages in a special order. The messages are stored in a linked list. To improve user experience, you want to reorder the messages so that the first message is followed by the last message, then the second message, then the second last message, and so on.This reordering helps highlight recent and older messages alternately.

🎯 Goal: Build a program that reorders a singly linked list in the pattern: first node, last node, second node, second last node, and so on.For example, if the list is 1 -> 2 -> 3 -> 4 -> 5 -> null, after reordering it should become 1 -> 5 -> 2 -> 4 -> 3 -> null.

📋 What You'll Learn

Create a linked list with nodes containing integer values

Use a variable to find the middle of the linked list

Reverse the second half of the linked list

Merge the two halves by alternating nodes

Print the reordered linked list in the format: value -> value -> ... -> null

💡 Why This Matters

🌍 Real World

Reordering linked lists is useful in applications like messaging apps, music playlists, or any system where alternating recent and older items improves user experience.

💼 Career

Understanding linked list manipulation is important for software engineers working on data structures, algorithms, and performance optimization.

1

Create the Linked List

Create a class called ListNode with a constructor that takes val and sets this.val and this.next to null. Then create a linked list with nodes having values 1, 2, 3, 4, and 5 linked in order, and assign the head node to a variable called head.

DSA Javascript

// Your code here

Hint

Define the ListNode class first. Then create nodes and link them by setting the next property.

2

Find the Middle of the Linked List

Create two variables called slow and fast and set both to head. Use a while loop with the condition fast !== null && fast.next !== null to move slow one step and fast two steps forward until the middle is found.

DSA Javascript

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

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

// Your code here

Hint

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

3

Reverse the Second Half of the List

Create a variable called prev and set it to null. Create a variable called curr and set it to slow. Use a while loop to reverse the list starting from curr by changing curr.next to prev, then move prev and curr forward until curr is null. After the loop, prev will be the head of the reversed second half.

DSA Javascript

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

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

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

// Your code here

Hint

Reverse the second half by changing the next pointers one by one.

4

Merge the Two Halves and Print the Result

Create two variables first and second and set them to head and prev respectively. Use a while loop with the condition second !== null && second.next !== null to merge nodes by alternating: save first.next and second.next in temporary variables, set first.next to second, then second.next to the saved first.next, and move first and second forward. Finally, print the reordered list in the format value -> value -> ... -> null.

DSA Javascript

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

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

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

let prev = null;
let curr = slow;
while (curr !== null) {
  let nextTemp = curr.next;
  curr.next = prev;
  prev = curr;
  curr = nextTemp;
}

// Your code here

Hint

Alternate nodes from the first half and reversed second half, then print the list.

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