Reorder Linked List in DSA Java - 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 reorderList method on the list 1 -> 2 -> 3 -> 4 -> 5 -> null?

DSA Java

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

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        // Find middle
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // Reverse second half
        ListNode prev = null, curr = slow.next;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        slow.next = null;
        // Merge two halves
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }

    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        ListNode 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);

        Solution sol = new Solution();
        sol.reorderList(head);
        printList(head);
    }
}

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

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

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

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

💡 Hint

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

The reorderList method splits the list into two halves, reverses the second half, and then merges nodes alternately from the first and reversed second half. For the input 1->2->3->4->5, the reordered list is 1->5->2->4->3->null.

🔧 Debug

intermediate

Identify the error in this reorderList implementation

What error will this code produce when reorderList is called on a list with nodes 1 -> 2 -> 3 -> null?

DSA Java

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode second = slow.next;
    slow.next = null;
    ListNode prev = null;
    while (second != null) {
        ListNode next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }
    ListNode first = head;
    while (prev != null) {
        ListNode tmp1 = first.next;
        ListNode tmp2 = prev.next;
        first.next = prev;
        prev.next = tmp1;
        first = tmp1;
        prev = tmp2;
    }
}

A NullPointerException

B IndexOutOfBoundsException

C No error, works correctly

D StackOverflowError

💡 Hint

Check what happens when first or prev becomes null inside the merge loop.

The code can cause NullPointerException because in the merge loop, first can become null before prev, and accessing first.next causes the exception.

🚀 Application

advanced

Reordering a Linked List with Even Number of Nodes

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

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

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

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

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

💡 Hint

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

For even nodes, the list is split into two halves (10->20 and 30->40), second half reversed (40->30), then merged alternately to get 10->40->20->30->null.

📝 Syntax

advanced

Identify the syntax error in this reorderList snippet

Which option contains the syntax error when trying to reverse the second half of the linked list?

DSA Java

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

A Incorrect variable name 'prev' instead of 'previous'

B Missing semicolon after ListNode nextTemp = curr.next

C Using '==' instead of '=' in curr.next = prev

D Missing braces around while loop body

💡 Hint

Check each line carefully for punctuation errors.

The line 'ListNode nextTemp = curr.next' is missing a semicolon at the end, causing a syntax error.

🧠 Conceptual

expert

Understanding the Time Complexity of Reorder List

What is the overall time complexity of the reorderList algorithm that splits the list, reverses the second half, and merges the two halves?

A O(log n)

B O(n log n)

C O(n^2)

D O(n)

💡 Hint

Consider how many times each node is visited during the process.

Each step (finding middle, reversing, merging) takes linear time, so overall complexity is O(n).

Practice

1. What is the main goal of the Reorder Linked List problem?

easy

A. Sort the linked list in ascending order

B. Rearrange the list so nodes alternate from start and end towards the center

C. Reverse the entire linked list

D. Remove duplicate nodes from the linked list

Solution

1. Step 1: Understand the problem requirement

   The problem asks to reorder the list so that nodes come alternately from the start and end, like L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ...

2. Step 2: Differentiate from other operations

   This is not sorting or reversing the whole list, but a specific rearrangement pattern.

3. Final Answer:

   Rearrange the list so nodes alternate from start and end towards the center -> Option B

4. Quick Check:

   Reorder = alternate start/end nodes [OK]

Hint: Think of weaving nodes from front and back alternately [OK]

Common Mistakes:

• Confusing reorder with sorting
• Trying to reverse the whole list only
• Ignoring the alternating pattern

2. Which Java code snippet correctly splits a linked list into two halves using slow and fast pointers?

easy

A. ListNode slow = head, fast = head; while(fast.next != null) { slow = slow.next; fast = fast.next; }

B. ListNode slow = head.next, fast = head; while(fast != null) { slow = slow.next; fast = fast.next.next; }

C. ListNode slow = head, fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

D. ListNode slow = head, fast = head.next; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

Solution

1. Step 1: Initialize pointers correctly

   Slow starts at head, fast starts at head.next to find middle for even length lists.

2. Step 2: Loop condition and pointer moves

   Loop while fast and fast.next are not null, move slow by one and fast by two nodes.

3. Final Answer:

   ListNode slow = head, fast = head.next; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } -> Option D

4. Quick Check:

   Slow at middle, fast moves twice [OK]

Hint: Start fast one step ahead to split even lists correctly [OK]

Common Mistakes:

• Starting fast at head causing wrong middle
• Incorrect loop conditions causing null pointer
• Moving fast by one instead of two

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

medium

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

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

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

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

Solution

1. Step 1: Identify nodes from start and end

   Start with 1 (head), then last node 5, then second node 2, then second last 4, then middle 3.

2. Step 2: Arrange nodes alternately

   Link nodes in order: 1 -> 5 -> 2 -> 4 -> 3 -> null.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Pick nodes alternately from front and back [OK]

Common Mistakes:

• Reversing entire list instead of reordering
• Skipping middle node placement
• Mixing node order incorrectly

4. Consider this buggy code snippet for reversing the second half of a linked list in reorder operation:

ListNode prev = null;
ListNode curr = mid.next;
while(curr != null) {
  ListNode nextTemp = curr.next;
  curr.next = prev;
  prev = curr;
  curr = nextTemp;
}
mid.next = prev;

What is the likely bug here?

medium

A. The prev pointer is not initialized correctly

B. The loop condition should be while(curr.next != null)

C. The mid.next should be set to null before reversing

D. The reversal logic is correct; no bug present

Solution

1. Step 1: Understand reversal impact on original list

   Before reversing second half, mid.next should be set to null to break the list and avoid cycles.

2. Step 2: Identify missing step causing cycle

   Without setting mid.next = null before reversal, the list may form a cycle causing infinite loops later.

3. Final Answer:

   The mid.next should be set to null before reversing -> Option C

4. Quick Check:

   Break list before reverse to avoid cycles [OK]

Hint: Always cut list at middle before reversing second half [OK]

Common Mistakes:

• Not breaking list causing infinite loops
• Changing loop condition incorrectly
• Misinitializing pointers

5. You have a linked list with nodes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null. After reordering, what will be the final list?

hard

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

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

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

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

Solution

1. Step 1: Split list into two halves

   First half: 1 -> 2 -> 3, second half: 4 -> 5 -> 6.

2. Step 2: Reverse second half

   Reversed second half: 6 -> 5 -> 4.

3. Step 3: Merge halves alternately

   Merge nodes alternately: 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null.

4. Final Answer:

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

5. Quick Check:

   Alternate front and reversed back nodes [OK]

Hint: Reverse second half, then weave nodes alternately [OK]

Common Mistakes:

• Not reversing second half before merging
• Merging nodes in wrong order
• Forgetting to terminate list properly