algoadvance

Leetcode 143. Reorder List

Problem Statement

You are given the head of a singly linked list head, 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:

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

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

Clarifying Questions

1. Q: Is the input list guaranteed to have at least one node? A: Yes, the input list is guaranteed to have at least one node.

2. Q: What should we return if the list has only one element? A: If the list has only one element, we do not need to make any changes. It should remain as is.

3. Q: What do we do if the list is empty? A: The problem guarantees at least one node, so this scenario does not need to be handled.

Strategy

To reorder the list as described, we can follow these steps:

1. Find the Middle: Use the slow and fast pointer approach to find the middle of the linked list. This will help us to split the list into two halves.

2. Reverse the Second Half: Reverse the second half of the linked list. This can be done using a standard linked list reversal algorithm.

3. Merge the Two Halves: Merge the two halves by alternating nodes from each half. Specifically, take a node from the first half, then a node from the reversed second half, and repeat.

Code

Here is the Java implementation of the given strategy:

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

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

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

        // Step 2: Reverse the second half of the linked list
        ListNode secondHalf = reverseList(slow.next);
        slow.next = null; // split the list into two halves

        // Step 3: Merge the two halves
        ListNode firstHalf = head;
        while (secondHalf != null) {
            ListNode temp1 = firstHalf.next;
            ListNode temp2 = secondHalf.next;

            firstHalf.next = secondHalf;
            secondHalf.next = temp1;

            firstHalf = temp1;
            secondHalf = temp2;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }
}

Time Complexity

• Finding the Middle: O(n) where n is the number of nodes in the list. We are traversing the list once.
• Reversing the Second Half: O(n/2) which simplifies to O(n). This involves traversing half of the list.
• Merging the Two Halves: O(n) as we are traversing through each node once.

Thus, the overall time complexity is O(n).

The space complexity is O(1) since we are doing everything in place and not using any extra space apart from a few pointers.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?