Reorder List - CPP Solution

1. Introduction

This blog post discusses a problem that involves reordering a singly linked list in a specific pattern. This problem tests one's understanding of linked list manipulation, including reversing a list and merging two lists.

Problem

Given the head of a singly linked list, the task is to reorder the list so that the first element is followed by the last element, then the second element followed by the second last, and so on.

Example:

List: L0 → L1 → … → Ln-1 → Ln

Reordered: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

2. Solution Steps

1. Find the middle of the linked list.

2. Reverse the second half of the list.

3. Merge the first half and the reversed second half.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to find the middle of the list
ListNode* findMiddle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Function to reverse a list
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head, *next = nullptr;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// Function to merge two lists
void mergeLists(ListNode* l1, ListNode* l2) {
    while (l1 && l2) {
        ListNode *temp1 = l1->next, *temp2 = l2->next;
        l1->next = l2;
        if (temp1 == nullptr) break;
        l2->next = temp1;
        l1 = temp1;
        l2 = temp2;
    }
}

// Function to reorder the list
void reorderList(ListNode* head) {
    if (!head || !head->next) return;

    ListNode* mid = findMiddle(head);
    ListNode* l1 = head;
    ListNode* l2 = mid->next;
    mid->next = nullptr;

    l2 = reverseList(l2);
    mergeLists(l1, l2);
}

// Function to print the linked list
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list
    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);

    reorderList(head);
    printList(head); // Expected output: 1 -> 5 -> 2 -> 4 -> 3 -> nullptr
    return 0;
}

Output:

1 -> 5 -> 2 -> 4 -> 3 -> nullptr

Explanation:

The reorderList function first finds the middle of the list, then reverses the second half. 

The next step involves merging the first half with the reversed second half. 

This approach rearranges the nodes in the desired order without altering the node values. 

The key steps involve typically linked list operations: finding the middle, reversing a list, and merging two lists.