Reorder List [Linked List]

143.Reorder List

Linked List

Two Pointers

Problem Statement:

Given a singly linked list head, reorder it to follow the pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …. Modify the list in-place and do not return anything.

Algorithm:

1. Use the fast-slow pointer technique to find the middle node of the linked list.
2. Reverse the second half of the list starting from the middle node.
3. Merge the two halves by alternating nodes from the first and second halves.

Complexity:

Time: O(n), where n is the number of nodes in the list. | Space: O(1), in-place modification of the list.

Java Implementation:

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;

        // Find the middle node using fast and slow pointers
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half of the list
        ListNode head2 = reverse(slow.next);
        slow.next = null; // Terminate the first half

        // Merge the two halves by alternating nodes
        while (head != null && head2 != null) {
            ListNode tmp1 = head.next;
            ListNode tmp2 = head2.next;
            head2.next = head.next;
            head.next = head2;
            head = tmp1;
            head2 = tmp2;
        }
    }

    // Helper method to reverse a linked list
    private ListNode reverse(ListNode n) {
        ListNode prev = null, cur = n;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
}
                

Python Implementation:

class Solution:
    def reorderList(self, head):
        if not head:
            return
        
        # Find the middle node
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half
        head2, slow.next = slow.next, None
        prev = None
        while head2:
            tmp = head2.next
            head2.next = prev
            prev = head2
            head2 = tmp

        # Merge two halves
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2
                

C++ Implementation:

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

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

        // Reverse the second half
        ListNode* head2 = reverse(slow->next);
        slow->next = nullptr;

        // Merge the two halves
        while (head && head2) {
            ListNode* tmp1 = head->next;
            ListNode* tmp2 = head2->next;
            head2->next = head->next;
            head->next = head2;
            head = tmp1;
            head2 = tmp2;
        }
    }

private:
    ListNode* reverse(ListNode* n) {
        ListNode* prev = nullptr, *cur = n;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
};