Reorder List medium

Problem Statement

Given a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices. Please note here that the indices are 1-based. For example, the linked list: 1->2->3->4->5 becomes 1->3->5->2->4.

Example 1

Input: head = [1,2,3,4,5] Output: [1,3,5,2,4]

Example 2

Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]

Steps

1. Find the middle of the linked list: Use slow and fast pointers. The slow pointer moves one step at a time, and the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

2. Reverse the second half of the linked list: Use a standard iterative reversal algorithm.

3. Merge the first and second halves: Interleave the nodes from the first and reversed second halves.

Explanation

The algorithm efficiently reorders the linked list by first finding the midpoint, then reversing the second half. This allows for a straightforward merging process to create the desired odd-even interleaving. The use of slow and fast pointers for midpoint finding is a classic technique for linked list manipulation, ensuring linear time complexity. Reversing the second half in-place avoids the need for extra space.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return; //Handle empty or single-node lists

        // Find the middle of the linked list
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Split the list into two halves
        ListNode* secondHalf = slow->next;
        slow->next = nullptr; //Important: Disconnect the first half from the second

        // Reverse the second half
        ListNode* prev = nullptr;
        ListNode* curr = secondHalf;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        secondHalf = prev; // secondHalf now points to the reversed second half


        // Merge the two halves
        ListNode* firstHalf = head;
        while (firstHalf && secondHalf) {
            ListNode* temp1 = firstHalf->next;
            ListNode* temp2 = secondHalf->next;
            firstHalf->next = secondHalf;
            secondHalf->next = temp1;
            firstHalf = temp1;
            secondHalf = temp2;
        }
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. Each step (finding the middle, reversing, merging) takes linear time.

• Space Complexity: O(1). The algorithm operates in-place; it doesn't use any extra space proportional to the input size. It uses a constant number of pointers.