143. Reorder List - Leetcode Solution

Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reorderList(self, head: 'Optional[ListNode]') -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return
        
        # Step 1: Find the middle
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Step 2: Reverse the second half
        prev = None
        curr = slow.next
        slow.next = None
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # Step 3: Merge two halves
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

// 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;
        
        // Step 1: Find the middle
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Step 2: Reverse the second half
        ListNode* prev = nullptr;
        ListNode* curr = slow->next;
        slow->next = nullptr;
        while (curr) {
            ListNode* next_temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next_temp;
        }
        
        // Step 3: Merge two halves
        ListNode* first = head;
        ListNode* second = prev;
        while (second) {
            ListNode* tmp1 = first->next;
            ListNode* tmp2 = second->next;
            first->next = second;
            second->next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
};

// Definition for singly-linked list.
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;
        
        // Step 1: Find the middle
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Step 2: Reverse the second half
        ListNode prev = null, curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        
        // Step 3: Merge two halves
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    if (!head || !head.next) return;
    
    // Step 1: Find the middle
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Step 2: Reverse the second half
    let prev = null, curr = slow.next;
    slow.next = null;
    while (curr) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    
    // Step 3: Merge two halves
    let first = head, second = prev;
    while (second) {
        let tmp1 = first.next;
        let tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
};

Problem Description

You are given the head of a singly linked list head. Your task is to reorder the list in-place such that the nodes are arranged in the following order:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
That is, after the first node, the last node comes, then the second node, then the second-last node, and so on, alternating from the start and the end of the list.

You must not modify the values in the nodes, only the nodes themselves can be changed.
Do not use extra space for another list; perform the reordering in-place.
There is only one valid solution for each input list.
Do not reuse any nodes; simply rearrange the existing ones.

Thought Process

At first glance, the problem looks like we need to alternate nodes from the start and end of the linked list. A brute-force approach might be to repeatedly traverse to the end for each step, but this would be very slow for large lists.

To optimize, we should look for a way to access both ends efficiently. Since it's a singly linked list, we can't traverse backwards, but if we reverse half the list, we can iterate from both ends in one pass.

The challenge is to do this in-place, without using extra memory for another list, and without changing node values. This suggests a three-step process: find the middle, reverse the second half, and then merge the two halves together.

Solution Approach

Step 1: Find the Middle of the List
- Use the "slow and fast pointer" technique.
- Move slow by one step and fast by two steps each time. When fast reaches the end, slow will be at the middle.
Step 2: Reverse the Second Half
- From the middle node, reverse the second half of the list.
- This way, the last node becomes the head of the reversed part, allowing us to traverse from both ends.
Step 3: Merge the Two Halves
- Iterate through the first half and the reversed second half, alternately linking nodes from each.
- Continue until all nodes are rearranged in the required order.

This approach ensures that no extra space is used and all node rearrangements are done in-place, as required by the problem.

Example Walkthrough

Let's use the input list: 1 → 2 → 3 → 4 → 5

Find the Middle:
- After moving slow and fast pointers, slow stops at node 3.
Reverse the Second Half:
- Second half is 4 → 5. After reversal: 5 → 4.
Merge Halves:
- First pointer starts at 1, second at 5.
- Link 1 → 5
- Link 5 → 2
- Link 2 → 4
- Link 4 → 3
- Final order: 1 → 5 → 2 → 4 → 3

Each step alternates nodes from the start and end, achieving the desired reordering.

Time and Space Complexity

Brute-force Approach:
- For each node, traversing to the end to find the next node: O(n²) time.
- Space: O(1), as no extra memory is used (if in-place).
Optimized Approach (Current Solution):
- Finding the middle: O(n)
- Reversing the second half: O(n)
- Merging the two halves: O(n)
- Total time complexity: O(n)
- Space complexity: O(1), as all operations are done in-place.

The optimized approach is efficient and meets the problem's constraints.

Summary

The problem requires reordering a singly linked list by alternating nodes from the start and end. The key insight is to reverse the second half of the list and then merge the two halves in-place. By using slow and fast pointers, in-place reversal, and careful merging, we achieve an O(n) time and O(1) space solution that is both efficient and elegant. This approach showcases classic linked list manipulation techniques and highlights the power of pointer operations in solving complex problems without extra memory.

AlgoMap.io

Want Help Cracking FAANG?