Reorder Linked List in DSA Java - 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 list so that the first message is followed by the last message, then the second message, then the second last message, and so on.

🎯 Goal: Build a Java program that reorders a singly linked list in the pattern: first node, last node, second node, second last node, etc.

📋 What You'll Learn

Create a singly linked list with nodes containing integer values

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

💡 Why This Matters

🌍 Real World

Reordering linked lists is useful in applications like messaging apps, music playlists, or any system where data needs to be displayed in a special alternating order.

💼 Career

Understanding linked list manipulation is important for software engineering roles that involve data structure optimization and algorithmic problem solving.

1

Create the Linked List

Create a class called ListNode with an integer val and a next pointer. Then create a linked list with nodes containing values 1, 2, 3, 4, and 5 linked in order, and assign the head node to a variable called head.

DSA Java

// Define ListNode class and create linked list with values 1 to 5
// Your code here

Hint

Define the ListNode class first. Then create nodes one by one and link them using the next pointer.

2

Find the Middle of the Linked List

Add code inside main to find the middle node of the linked list using two pointers called slow and fast. Initialize both to head. Move slow by one step and fast by two steps until fast reaches the end or fast.next is null. After the loop, slow should point to the middle node.

DSA Java

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

public class Main {
    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);

        // Find middle node using slow and fast pointers
        // Your code here
    }
}

Hint

Use two pointers starting at head. Move slow by one and fast by two steps inside a while loop.

3

Reverse the Second Half of the List

Add code after finding the middle to reverse the linked list starting from slow. Use three pointers: prev initialized to null, curr initialized to slow, and nextTemp for temporary storage. Iterate while curr is not null, reverse the next pointer of curr to prev, then move prev and curr forward. After the loop, prev will be the head of the reversed second half.

DSA Java

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

public class Main {
    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);

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

        // Reverse the second half starting from slow
        // Your code here
    }
}

Hint

Use a loop to reverse the pointers of the second half starting from slow. Keep track of previous and current nodes.

4

Merge the Two Halves and Print the Result

Merge the first half starting from head and the reversed second half starting from prev by alternating nodes. Use two pointers first and second. While second.next is not null, save the next nodes, link first.next to second, then second.next to the saved next of first. Move first and second forward. Finally, print the reordered list nodes' values separated by -> and ending with null.

DSA Java

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

public class Main {
    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);

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

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

        // Merge the two halves and print the reordered list
        // Your code here
    }
}

Hint

Alternate nodes from the first half and reversed second half. Then print all node values separated by -> and end with null.

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