143. Reorder List

MediumStackRecursionLinked ListTwo Pointers
Leetcode Link

Problem Description

The problem provides a singly linked list with nodes labeled from L0 to Ln. The task is to reorder the list in a specific manner without changing the node values but only by rearranging the nodes. The reordered list should follow a pattern where the first node is followed by the last node, then the second node is followed by the second to last node, and this pattern continues until all nodes have been reordered. This results in a list that starts at the head, alternates nodes from the start and end of the list, and meets in the middle.

Intuition

The solution can be broken down into several logical steps:

  1. Finding the middle of the list: We use the fast and slow pointer technique to find the middle of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle of the list.

  2. Reversing the second half of the list: Once we have the middle of the list, we reverse the second half. This is done iteratively by initializing pointers and rearranging the links between nodes in the second half of the list.

  3. Merging the two halves: With the second half reversed, we now have two lists: the first half in the original order and the second half in reverse order. We merge the two lists by alternating nodes from each, starting with the first node of the first half and inserting the first node of the second half after it, followed by the second node of the first half, and so on, until all the nodes from the second half have been inserted into the first half.

The provided solution follows these steps to achieve the desired list reordering.

Learn more about Stack, Recursion, Linked List and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which two pointer technique does Quick Sort use?

Solution Approach

The implementation of the solution can be outlined in the below steps corresponding to the intuition described earlier:

  1. Using Two Pointers to Find the Middle: We initialize two pointers, both starting at the head of the list. The slow pointer advances one node at a time, while the fast pointer advances two nodes at a time. When the fast pointer either reaches the end of the list or the node before the end, the slow pointer will be at the middle of the list. The loop while fast.next and fast.next.next: ensures we stop at the correct position in the list.

  2. Reversing the Second Half: In order to reverse the second half of the list, we first set slow.next to None to mark the end of the first half of the list. We then use three pointer variables (cur, pre, and t) to reverse the second half of the list. cur starts at the first node of the second half, while pre is set to None to mark the new end of the list. We then iterate through the second half using while cur:, in each iteration, we temporarily store the next node using t = cur.next, point the current node to pre, and then move pre and cur forward.

  3. Merging the Two Halves: We now have two lists: the first half, starting at head, and the second half, starting at pre, which is the reverse of the original second half. We merge these two half-lists by iterating through them, taking one node from each list and adjusting the pointers to merge them into a single list. The loop while pre: allows us to do just that. During each iteration, we store the next node of pre in t, then we link pre to the next of the current node in the first list (cur.next). After updating cur.next to pre, we advance cur and pre using the stored values.

The final result of these steps is a reordered list in the desired pattern: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... until all nodes are repositioned accordingly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Consider a linked list with nodes L0 โ†’ L1 โ†’ L2 โ†’ L3 โ†’ L4. We want to reorder this list following the specific pattern described in the problem: L0 โ†’ L4 โ†’ L1 โ†’ L3 โ†’ L2.

Step 1: Finding the Middle of the List We use two pointers, slow and fast. Initially, both pointers start at L0. As we iterate through the list:

  • In the first step, slow is at L0, and fast is at L1.
  • In the second step, slow is at L1, and fast is at L3.
  • In the third step, slow is at L2, and fast is at the end (null), so slow is now at the middle of the list.

The list is now considered in two parts: the first half is L0 โ†’ L1 โ†’ L2, and the second half, starting at L3, needs to be reversed.

Step 2: Reversing the Second Half Starting from L3, we reverse the second half of the list. We set slow.next to None to mark the end of the first half to get L0 โ†’ L1 โ†’ L2 and L3 โ†’ L4.

  • cur begins at L3, and pre is None.
  • We swap the next of cur (which is L4) to point to pre and advance pre to be L3 and cur to be L4.
  • Now cur is L4, and we point L4 to the new pre (which is L3), making pre equal to L4 and cur to None.

After completing this process, the second half is reversed, and our lists look like this: L0 โ†’ L1 โ†’ L2 and L4 โ†’ L3.

Step 3: Merging the Two Halves We have two sublists, and now we merge them in the alternate sequence:

  • Start with head at L0 and pre at L4.
  • Save the next of head (L1) and link head to pre (L4). List after this step: L0 โ†’ L4.
  • Advance head to saved next (L1) and pre to next in the reversed list (L3).
  • Save next of head again (L2) and link head to pre (L3). List after this step: L0 โ†’ L4 โ†’ L1 โ†’ L3.
  • Advance head to saved next (L2), and since pre has no next (null), we've finished merging.

The final reordered list is L0 โ†’ L4 โ†’ L1 โ†’ L3 โ†’ L2, which matches the required pattern.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def reorderList(self, head: ListNode) -> None:
9        """
10        This function takes the head of a singly linked list and reorders it in-place
11        so that the nodes are in a specific sequence: L0 โ†’ Ln โ†’ L1 โ†’ Ln - 1 โ†’ L2 โ†’ Ln - 2 โ†’ โ€ฆ
12        You must do this without altering the values in the list's nodes, i.e., only nodes themselves may be changed.
13        """
14
15        # Use the fast and slow pointer technique to find the middle of the linked list
16        fast = slow = head
17        while fast and fast.next:
18            slow = slow.next
19            fast = fast.next.next
20      
21        # Split the linked list into two halves
22        second_half = slow.next
23        slow.next = None
24      
25        # Reverse the second half of the linked list
26        previous = None
27        current = second_half
28        while current:
29            temp = current.next
30            current.next = previous
31            previous, current = current, temp
32      
33        # Merge the two halves, inserting nodes from the second half into the first
34        first_half = head
35        second_half = previous # This is now the head of the reversed second half.
36        while second_half:
37            temp1 = first_half.next
38            temp2 = second_half.next
39          
40            first_half.next = second_half
41            second_half.next = temp1
42          
43            first_half, second_half = temp1, temp2
44      
45        # The linked list is now re-ordered in the required pattern
46
1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11class Solution {
12    public void reorderList(ListNode head) {
13        // Step 1: Use two-pointers to find the middle of the linked list
14        ListNode fastPointer = head, slowPointer = head;
15        // fastPointer moves twice as fast as the slowPointer
16        while (fastPointer.next != null && fastPointer.next.next != null) {
17            slowPointer = slowPointer.next;
18            fastPointer = fastPointer.next.next;
19        }
20
21        // Step 2: Split the list into two and reverse the second half
22        // Now, slowPointer is at the middle of the list
23        ListNode current = slowPointer.next; // This is the start of the second half
24        slowPointer.next = null; // Split the list into two
25      
26        ListNode previous = null;
27        // Reverse the second half of the list
28        while (current != null) {
29            ListNode temp = current.next;
30            current.next = previous;
31            previous = current;
32            current = temp;
33        }
34
35        // Step 3: Merge the two halves back together
36        current = head; // Reset current to the start of the first half
37      
38        // Traverse the first and the reversed second half together
39        while (previous != null) {
40            // 'previous' traverses the reversed list
41            ListNode temp = previous.next;
42            // Link the current node of the first half to the current node of the reversed second half
43            previous.next = current.next;
44            // Link the current node of the reversed second half to the next node in the first half
45            current.next = previous;
46          
47            // Move to the next node in the first half
48            current = previous.next;
49            // Proceed to the next node in the reversed second half
50            previous = temp;
51        }
52    }
53}
54
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    void reorderList(ListNode* head) {
14        if (!head || !(head->next) || !(head->next->next)) {
15            // If the list has 0, 1, or 2 nodes, no reordering is needed.
16            return;
17        }
18
19        // Use the fast and slow pointer technique to find the middle of the list.
20        ListNode* fast = head;
21        ListNode* slow = head;
22        while (fast->next && fast->next->next) {
23            slow = slow->next; // Move one step.
24            fast = fast->next->next; // Move two steps.
25        }
26
27        // Split the list into two halves.
28        ListNode* secondHalf = slow->next;
29        slow->next = nullptr; // Terminate first half.
30
31        // Reverse the second half of the list.
32        ListNode* prev = nullptr;
33        while (secondHalf) {
34            ListNode* temp = secondHalf->next;
35            secondHalf->next = prev;
36            prev = secondHalf;
37            secondHalf = temp;
38        }
39
40        // Start merging the first and second halves one node at a time.
41        ListNode* firstHalf = head;
42        ListNode* secondHalfHead = prev; // Points to the head of the reversed second half.
43        while (secondHalfHead) {
44            ListNode* temp = secondHalfHead->next;
45            secondHalfHead->next = firstHalf->next;
46            firstHalf->next = secondHalfHead;
47
48            // Move pointers ahead.
49            firstHalf = secondHalfHead->next; // Moved to the next of the newly added node.
50            secondHalfHead = temp; // Moving to the next node in the reversed half.
51        }
52    }
53};
54
1// Function to reorder a linked list in-place such that the nodes are in a specific order
2function reorderList(head: ListNode | null): void {
3    let slowPointer = head; // This will be used to find the middle of the list
4    let fastPointer = head; // This will go twice as fast to find the end quickly
5
6    // First, split the list into two halves. The slowPointer will end up at the midpoint
7    while (fastPointer != null && fastPointer.next != null) {
8        slowPointer = slowPointer.next;
9        fastPointer = fastPointer.next.next;
10    }
11
12    // Reverse the second half of the list using the standard three-pointer approach
13    let nextNode = slowPointer.next;
14    slowPointer.next = null; // This null will be the new end of the first half
15    while (nextNode != null) {
16        [nextNode.next, slowPointer, nextNode] = [slowPointer, nextNode, nextNode.next]; // Reverse the pointers in the second half
17    }
18
19    // Now merge the two halves, weaving them together one by one
20    let leftPointer = head; // This will traverse the first half
21    let rightPointer = slowPointer; // This will traverse the reversed second half
22
23    // Weaving the two halves together
24    while (rightPointer.next != null) {
25        let leftNext = leftPointer.next; // Store the next node in first half
26        leftPointer.next = rightPointer; // Link the first node from second half
27        rightPointer = rightPointer.next; // Move to the next node in second half
28        leftPointer.next.next = leftNext; // Connect the next node from first half
29        leftPointer = leftPointer.next.next; // Move to the next node in merged list
30    }
31}
32
Not Sure What to Study? Take the 2-min Quiz๏ผš

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Time and Space Complexity

The given Python code performs a reordering of a singly-linked list such that the node from the end is alternated with the node from the beginning. Here's the breakdown of its computational complexity:

Time Complexity:

The time complexity of the code is determined by several sequential operations:

  1. Finding the Middle of the List: The first while loop uses the fast and slow pointers to find the middle of the list. Since the fast pointer moves at twice the speed of the slow pointer, the loop runs in O(n/2) where n is the number of nodes in the list. This simplifies to O(n).

  2. Reversing the Second Half of the List: The second while loop reverses the second half of the list, from the node after the middle to the end of the list. This portion of the list has n/2 nodes, so the loop runs in O(n/2), which also simplifies to O(n).

  3. Merging Two Halves: The third while loop merges the two halves of the list. Since it processes each node exactly once, its time complexity is O(n).

Overall, the time complexity is O(n) + O(n) + O(n) which simplifies to O(n) because constants are dropped in Big O notation.

Space Complexity:

The space complexity refers to the additional space used by the algorithm, not including the input itself:

  1. Pointers: The algorithm uses a constant number of pointers (fast, slow, cur, pre, t) whose space usage does not depend on the input size.

  2. In-Place Operations: The list is modified in-place, with nodes' next pointers being changed to reorder it, but no additional data structures are used that grow with the input size.

Thus, the space complexity is O(1) since only a constant amount of extra space is used aside from the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ