Reorder Linked List in DSA C# - Build from Scratch

Reorder Linked List

📖 Scenario: You are working on a program that manages a singly linked list of numbers. Sometimes, you want to reorder the list so that the nodes are arranged in a special pattern: first node, last node, second node, second last node, and so on.This helps in scenarios like arranging tasks or events in a balanced way from both ends.

🎯 Goal: Build a program that takes a singly linked list and reorders it in the pattern: first node, last node, second node, second last node, etc.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 singly linked list with exact nodes and values

Find the middle of the linked list

Reverse the second half of the list

Merge the two halves in the required order

Print the reordered linked list

💡 Why This Matters

🌍 Real World

Reordering linked lists is useful in scheduling tasks, balancing data streams, or preparing data for special display orders.

💼 Career

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

1

Create the Linked List

Create a singly linked list with nodes containing these exact values in order: 1, 2, 3, 4, 5. Use the class ListNode with an integer val and a next pointer. Create a variable called head pointing to the first node.

DSA C#

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

// Create the linked list nodes and link them
// Your code here

Hint

Start by creating the first node with value 1 and assign it to head. Then link each next node with the given values.

2

Find the Middle of the List

Create two pointers called slow and fast both starting at head. Move slow by one step and fast by two steps in a loop until fast reaches the end or fast.next is null. This will find the middle node. After the loop, slow should point to the middle node.

DSA C#

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

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 the middle node using slow and fast pointers
// Your code here

Hint

Use two pointers starting at the head. Move slow by one and fast by two steps until fast reaches the end.

3

Reverse the Second Half

Reverse the linked list starting from the node slow (middle node) to the end. Create a variable prev initialized to null. Use a loop to reverse the links: for each node, store next, point node.next to prev, then move prev and node forward. After the loop, prev will be the head of the reversed second half.

DSA C#

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

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 links starting from slow. Keep track of previous node and current node.

4

Merge the Two Halves and Print

Merge the first half starting from head and the reversed second half starting from prev. Use two pointers first and second. Alternate linking nodes from first and second until second is null. Then print the reordered list using a loop that prints each node's val followed by ->, ending with null.

DSA C#

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

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

Use two pointers to merge nodes from the first half and reversed second half alternately. Then print the list by traversing from head.

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