Reorder Linked List in DSA C - Build from Scratch

Reorder Linked List

📖 Scenario: You are working on a program that manages a list of tasks. The tasks are stored in a linked list in the order they were added. Sometimes, you want to reorder the list so that the first task is followed by the last task, then the second task, then the second last task, and so on.This helps to balance the tasks between the start and the end of the list.

🎯 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 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 scheduling tasks, balancing workloads, or rearranging data for better access patterns.

💼 Career

Understanding linked list manipulation is important for software engineers working on low-level data structures, embedded systems, or performance-critical applications.

1

Create the linked list

Create a struct called Node with an int data and a Node* called next. Then create 5 nodes with values 1, 2, 3, 4, 5 linked together in that order. Store the head of the list in a variable called head.

DSA C

// Define struct Node and create linked list with nodes 1 to 5
// Your code here

Hint

Start by defining the Node struct with data and next. Then create each node with malloc and link them by setting the next pointers.

2

Find the middle of the linked list

Add code 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 C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    Node* second = (Node*)malloc(sizeof(Node));
    second->data = 2;
    Node* third = (Node*)malloc(sizeof(Node));
    third->data = 3;
    Node* fourth = (Node*)malloc(sizeof(Node));
    fourth->data = 4;
    Node* fifth = (Node*)malloc(sizeof(Node));
    fifth->data = 5;

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    fifth->next = NULL;

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

    return 0;
}

Hint

Use two pointers starting at the head. Move slow by one node and fast by two nodes in a loop until fast reaches the end.

3

Reverse the second half of the list

Reverse the linked list starting from the node pointed to by slow. Use three pointers: prev initialized to NULL, curr initialized to slow, and next for temporary storage. Iterate until curr is NULL, reversing the next pointers. After the loop, prev will be the head of the reversed second half. Store it in a variable called second.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    Node* second = (Node*)malloc(sizeof(Node));
    second->data = 2;
    Node* third = (Node*)malloc(sizeof(Node));
    third->data = 3;
    Node* fourth = (Node*)malloc(sizeof(Node));
    fourth->data = 4;
    Node* fifth = (Node*)malloc(sizeof(Node));
    fifth->data = 5;

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    fifth->next = NULL;

    Node* slow = head;
    Node* 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

    return 0;
}

Hint

Use a loop to reverse the list starting from slow. Keep track of previous, current, and next nodes to reverse the links.

4

Merge the two halves and print the reordered list

Merge the first half starting from head and the reversed second half starting from second by alternating nodes. Use two pointers first and second. In each iteration, save the next nodes, link first->next to second, then second->next to the saved next of first. Move first and second forward. After merging, print the reordered list by traversing from head and printing each node's data followed by ->. End with NULL.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    Node* second = (Node*)malloc(sizeof(Node));
    second->data = 2;
    Node* third = (Node*)malloc(sizeof(Node));
    third->data = 3;
    Node* fourth = (Node*)malloc(sizeof(Node));
    fourth->data = 4;
    Node* fifth = (Node*)malloc(sizeof(Node));
    fifth->data = 5;

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    fifth->next = NULL;

    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node* prev = NULL;
    Node* curr = slow;
    Node* next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    Node* second = prev;

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

    return 0;
}

Hint

Alternate nodes from the first half and reversed second half by adjusting next pointers. Then print the list by traversing from head.

Practice

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

easy

A. To rearrange the list so nodes alternate from start and end

B. To sort the linked list in ascending order

C. To reverse the entire linked list

D. To remove duplicate nodes from the list

Solution

1. Step 1: Understand the reorder pattern

   The reorder linked list operation rearranges nodes so that the first node is followed by the last node, then the second node, then the second last node, and so on.

2. Step 2: Differentiate from other operations

   This is different from sorting, reversing, or removing duplicates because it mixes nodes from start and end alternatively.

3. Final Answer:

   To rearrange the list so nodes alternate from start and end -> Option A

4. Quick Check:

   Reorder = 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 reversing the list
• Assuming reorder removes duplicates

2. Which of the following C code snippets correctly finds the middle node of a singly linked list for reordering?

easy

A. while (fast && fast->next) { fast = fast->next; slow = slow->next; }

B. while (slow && slow->next) { fast = fast->next; slow = slow->next->next; }

C. while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }

D. while (fast && slow) { slow = slow->next->next; fast = fast->next->next; }

Solution

1. Step 1: Identify the fast and slow pointer technique

   To find the middle node, fast pointer moves two steps, slow pointer moves one step until fast reaches end.

2. Step 2: Check each option for correct pointer movement

   while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } correctly moves fast by two and slow by one. Others have incorrect pointer movements causing errors or wrong middle.

3. Final Answer:

   while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } -> Option C

4. Quick Check:

   Fast moves 2 steps, slow moves 1 step [OK]

Hint: Fast pointer moves twice as fast as slow pointer [OK]

Common Mistakes:

• Swapping fast and slow pointer movements
• Not checking fast->next before fast->next->next
• Using slow pointer to move two steps

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

medium

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern on the list

   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. So reordered list is 1 -> 5 -> 2 -> 4 -> 3 -> NULL.

3. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> NULL -> Option D

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Alternate nodes from start and end [OK]

Common Mistakes:

• Reversing the entire list instead
• Keeping original order unchanged
• Skipping nodes or mixing order

4. Consider this buggy C code snippet for reordering a linked list. What is the main error?

void reorderList(Node* head) {
  Node *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next;
  }
  // further code omitted
}

medium

A. Fast pointer moves only one step instead of two

B. Slow pointer moves two steps instead of one

C. Missing check for head being NULL

D. Using wrong variable names for pointers

Solution

1. Step 1: Analyze pointer movements in the loop

   Fast pointer should move two steps to find middle, but here it moves only one step.

2. Step 2: Identify impact of incorrect fast pointer movement

   This causes slow pointer to not reach the true middle, breaking reorder logic.

3. Final Answer:

   Fast pointer moves only one step instead of two -> Option A

4. Quick Check:

   Fast must move 2 steps, not 1 [OK]

Hint: Fast pointer moves twice as fast as slow [OK]

Common Mistakes:

• Not moving fast pointer two steps
• Ignoring NULL checks
• Confusing slow and fast pointer roles

5. You have a linked list: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULL. After reordering, what will be the list? Also, explain why the middle node is chosen as it is.

hard

A. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 40 because it's the node after center

B. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length

C. 10 -> 50 -> 20 -> 40 -> 30 -> 60 -> NULL; middle is 30 because it's the exact center

D. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 20 because it's the first half's end

Solution

1. Step 1: Find the middle node for even length list

   For 6 nodes, middle is node 3 (value 30) because slow pointer stops at exact center when fast moves two steps.

2. Step 2: Apply reorder pattern

   Reorder alternates nodes from start and end: 10, 60, 20, 50, 30, 40.

3. Final Answer:

   10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length -> Option B

4. Quick Check:

   Middle at center, reorder alternates front and back [OK]

Hint: Middle is center node; reorder alternates front and back [OK]

Common Mistakes:

• Choosing wrong middle for even length
• Mixing reorder order
• Confusing node positions