Reorder Linked List in DSA C#

Mental Model

We rearrange a linked list so nodes come from the start and end alternately, meeting in the middle.

Analogy: Imagine lining up people from two ends of a line to form a new line by picking one from the front, then one from the back, and so on.

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

Dry Run Walkthrough

Input: list: 1->2->3->4->5

Goal: Rearrange to 1->5->2->4->3

Step 1: Find middle node using slow and fast pointers

1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑slow, ↑fast

Why: We need to split the list into two halves at the middle

Step 2: Split list into two halves at middle

First half: 1 -> 2 -> 3 -> null
Second half: 4 -> 5 -> null

Why: Separating helps to reverse the second half independently

Step 3: Reverse second half

Second half reversed: 5 -> 4 -> null

Why: Reversing allows easy alternating merge from front and back

Step 4: Merge first half and reversed second half alternately

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

Why: Alternating nodes from front and back achieves the reorder

Result:

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

Annotated Code

DSA C#

using System;

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

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) return;

        // Find middle of the list
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next; // advance slow by one
            fast = fast.next.next; // advance fast by two
        }

        // Split and reverse second half
        ListNode second = slow.next;
        slow.next = null; // break first half
        second = ReverseList(second); // reverse second half

        // Merge two halves
        ListNode first = head;
        while (second != null) {
            ListNode temp1 = first.next; // save next of first
            ListNode temp2 = second.next; // save next of second

            first.next = second; // link first to second
            second.next = temp1; // link second to next of first

            first = temp1; // move first forward
            second = temp2; // move second forward
        }
    }

    private ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next; // save next
            curr.next = prev; // reverse pointer
            prev = curr; // move prev forward
            curr = nextTemp; // move curr forward
        }
        return prev;
    }

    public static void PrintList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            Console.Write(curr.val);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }

    public static void Main() {
        // Create list 1->2->3->4->5
        ListNode head = new ListNode(1,
            new ListNode(2,
                new ListNode(3,
                    new ListNode(4,
                        new ListNode(5)))));

        Console.WriteLine("Original list:");
        PrintList(head);

        Solution sol = new Solution();
        sol.ReorderList(head);

        Console.WriteLine("Reordered list:");
        PrintList(head);
    }
}

while (fast.next != null && fast.next.next != null) { slow = slow.next; // advance slow by one fast = fast.next.next; // advance fast by two }

Find middle node by moving slow one step and fast two steps until fast reaches end

slow.next = null; // break first half second = ReverseList(second); // reverse second half

Split list and reverse second half for merging

while (second != null) { ListNode temp1 = first.next; // save next of first ListNode temp2 = second.next; // save next of second first.next = second; // link first to second second.next = temp1; // link second to next of first first = temp1; // move first forward second = temp2; // move second forward }

Merge nodes alternately from first and reversed second half

while (curr != null) { ListNode nextTemp = curr.next; // save next curr.next = prev; // reverse pointer prev = curr; // move prev forward curr = nextTemp; // move curr forward }

Reverse linked list by changing next pointers

Output

Original list:

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

Reordered list:

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 C#

if (head == null || head.next == null) return;

Single node list

Function returns immediately without changes

DSA C#

if (head == null || head.next == null) return;

Two node list

List remains the same as reorder does not change order

DSA C#

while (fast.next != null && fast.next.next != null) { ... }

When to Use This Pattern

When asked to reorder a linked list by alternating nodes from front and back, use the pattern of finding the middle, reversing the second half, then merging alternately.

Common Mistakes

Mistake: Not breaking the list into two halves before reversing second half
Fix: Set slow.next = null to split the list before reversing

Mistake: Losing track of next nodes during merge causing cycles or lost nodes
Fix: Always save next pointers before changing links during merge

Summary

Rearranges a linked list so nodes alternate from front and back.

Use when you need to reorder a list in a specific alternating pattern without extra space.

The key is to split the list, reverse the second half, then merge nodes alternately.

Practice

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

easy

A. Reverse the entire linked list

B. Sort the linked list in ascending order

C. Rearrange the list so nodes alternate from start and end

D. Remove duplicate nodes from the list

Solution

1. Step 1: Understand the problem statement

   The problem asks to reorder the linked list so that nodes are arranged by alternating from the start and the end of the list.

2. Step 2: Differentiate from other operations

   This is not sorting or reversing the whole list, but a specific pattern: first node, last node, second node, second last node, and so on.

3. Final Answer:

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

4. Quick Check:

   Reorder means alternate start and end nodes [OK]

Hint: Reorder means alternate nodes from front and back [OK]

Common Mistakes:

• Confusing reorder with sorting
• Thinking reorder means full reversal
• Ignoring the alternating pattern

2. Which of the following C# code snippets correctly declares a singly linked list node class used in reorder linked list problems?

easy

A. public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } }

B. class Node { int val; Node next; Node(int x) { val = x; next = null; } }

C. public struct ListNode { public int val; public ListNode next; }

D. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }

Solution

1. Step 1: Check for public accessibility and constructor

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } correctly declares a public class with public fields and a constructor initializing value and next pointer.

2. Step 2: Identify missing public keywords and struct misuse

   Options A and D miss public keywords making fields inaccessible; C uses struct which is not typical for linked list nodes.

3. Final Answer:

   public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; next = null; } } -> Option A

4. Quick Check:

   Public class with constructor and public fields [OK]

Hint: Use public class with constructor and public fields [OK]

Common Mistakes:

• Omitting public keyword for fields
• Using struct instead of class
• Missing constructor initialization

3. Given the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null, what will be the list after applying the reorder linked list 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 the reorder pattern

   The reorder pattern takes first node, last node, second node, second last node, and so on.

2. Step 2: Apply pattern to given list

   Start with 1, then 5, then 2, then 4, then 3 remains in the middle.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Alternate nodes from front and back [OK]

Common Mistakes:

• Reversing entire list instead of reordering
• Not alternating nodes correctly
• Leaving list unchanged

4. Consider this C# code snippet for reordering a linked list. What is the bug?

public void ReorderList(ListNode head) {
  if (head == null) return;
  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  ListNode second = ReverseList(slow);
  ListNode first = head;
  while (second != null) {
    ListNode temp1 = first.next;
    ListNode temp2 = second.next;
    first.next = second;
    second.next = temp1;
    first = temp1;
    second = temp2;
  }
}

medium

A. The ReverseList method is missing

B. The middle node is included in the reversed second half causing cycle

C. The fast pointer initialization is incorrect

D. The loop condition should be while (second.next != null)

Solution

1. Step 1: Analyze slow pointer position after loop

   After the loop, slow points to the middle node, which is included in the reversed second half.

2. Step 2: Understand consequence of including middle node

   Including the middle node causes the merged list to have a cycle or incorrect links because the middle node is connected twice.

3. Final Answer:

   The middle node is included in the reversed second half causing cycle -> Option B

4. Quick Check:

   Exclude middle node before reversing second half [OK]

Hint: Exclude middle node before reversing second half [OK]

Common Mistakes:

• Not splitting list before reversing second half
• Incorrect loop conditions
• Assuming ReverseList is missing error

5. You have a linked list with nodes: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null. After applying the reorder linked list algorithm, what is the correct final list?

hard

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern for even length list

   For even nodes, reorder alternates first and last nodes: 10, 60, 20, 50, 30, 40.

2. Step 2: Apply the pattern to given list

   Start with 10, then 60, then 20, then 50, then 30, then 40, ending with null.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes for even length [OK]

Hint: Alternate nodes from front and back for even length [OK]

Common Mistakes:

• Reversing entire list instead of reordering
• Not handling even length correctly
• Leaving list unchanged