algoadvance

Leetcode 143. Reorder List

Problem Statement:

Given a singly linked list L, reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

You may not modify the values in the list’s nodes, only nodes themselves may be changed.

Example:

Given 1->2->3->4, reorder it to 1->4->2->3.

Given 1->2 ->3->4->5, reorder it to 1->5->2->4->3.

Clarifying Questions:

  1. Input Constraints:
    • Is the input list always of non-zero length, or do we have to handle an empty list?
    • What about lists with only one element? Do we need to perform any reordering?
  2. Output Format:
    • Should the reordered list be returned or modified in place?
  3. Time Complexity Constraints:
    • Are there any specific time or space complexity requirements?

Based on typical requirements for such problems:

Strategy:

To reorder the list as requested, we can break the problem into the following steps:

  1. Find the Middle of the Linked List:
    • We can use the slow and fast pointer technique to locate the middle of the list.
  2. Reverse the Second Half of the List:
    • Once the middle is found, split the list into two halves and reverse the second half of the list.
  3. Merge the Two Halves:
    • Alternate nodes from the first half and the reversed second half until one of the halves is exhausted.

Code Implementation:

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        // Step 1: Find the middle of the list using slow and fast pointers
        ListNode* slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse the second half
        ListNode* prev = nullptr;
        ListNode* curr = slow->next;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        // Step 3: Merge the two halves
        slow->next = nullptr;
        ListNode* first = head;
        ListNode* second = prev; // 'prev' is now the head of the reversed second half
        while (second) {
            ListNode* temp1 = first->next;
            ListNode* temp2 = second->next;

            first->next = second;
            second->next = temp1;

            first = temp1;
            second = temp2;
        }
    }
};

// Helper function to print the list (for testing purposes)
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "NULL" << std::endl;
}

int main() {
    Solution solution;

    // Example usage:
    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);

    std::cout << "Original list: ";
    printList(head);

    solution.reorderList(head);

    std::cout << "Reordered list: ";
    printList(head);

    return 0;
}

Time Complexity:

The overall time complexity of the solution is O(n).

Space Complexity:

This solution meets the criteria for modifying the list in-place with linear time complexity and constant extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI