Reorder List medium

Problem Statement

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

L₀ → L₁ → … → Lₙ₋₁ → Lₙ

Reorder the list to be on the following form:

L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → …

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 a slow and fast pointer technique. 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: Iteratively reverse the nodes from the middle to the end.

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

Explanation

The core idea is to split the linked list into two halves, reverse the second half, and then merge them alternately. The slow-fast pointer approach efficiently finds the middle without needing to know the list's length beforehand. Reversing the second half is a standard linked list operation. Finally, merging requires careful pointer manipulation to correctly link the nodes.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return; //Handle empty or single-node lists

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

        // 2. Reverse the second half
        ListNode prev = null, curr = slow, nextTemp;
        while (curr != null) {
            nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // 3. Merge the first and reversed second halves
        ListNode first = head, second = prev;
        while (second.next != null) {
            ListNode temp1 = first.next;
            ListNode temp2 = second.next;

            first.next = second;
            second.next = temp1;

            first = temp1;
            second = temp2;
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse the list three times: finding the middle, reversing the second half, and merging the halves.

• Space Complexity: O(1). The algorithm uses only a constant amount of extra space for pointers.