Reorder List medium

Problem Statement

You are given the head of a singly linked list. The list can be represented as:

L0 → L1 → L2 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

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 1

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

Example 2

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

Steps

1. Find the middle of the linked list: Use slow and fast pointers to find the middle node.
2. Reverse the second half of the linked list: Iteratively reverse the links from the middle node onwards.
3. Merge the first and reversed second halves: Iteratively merge the nodes from the first and reversed second halves, weaving them together.

Explanation

The algorithm efficiently reorders the linked list in O(n) time and O(1) space. Finding the middle takes linear time. Reversing the second half also takes linear time. Finally, merging the two halves also takes linear time. No extra space is used beyond a few pointers.

Let's trace Example 1 ([1,2,3,4]):

1. Find Middle: Slow and fast pointers start at head. Slow moves one step, fast moves two. They meet at node 2.
2. Reverse Second Half: The second half is [3, 4]. Reversing it gives [4, 3].
3. Merge:
   • Connect head (1) to the tail of the reversed second half (4).
   • Connect the next node of head (2) to the head of the reversed second half (3).
   • The next node of 2 (which is initially null) is set to null. The next node of 4 is also set to null to finish the reordering. The result is [1,4,2,3].

Code

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) return;

        // Find the middle of the linked list
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half of the linked list
        ListNode prev = null, curr = slow.next, temp;
        slow.next = null; // Disconnect the first and second halves
        while (curr != null) {
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        // Merge the first and reversed second halves
        ListNode first = head, second = prev;
        ListNode firstNext, secondNext;
        while (second != null) {
            firstNext = first.next;
            secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }
}

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 uses only a constant number of pointers.