grid47 Exploring patterns and algorithms
Oct 23, 2024
7 min read
Solution to LeetCode 143: Reorder List Problem
You are given the head of a singly linked list. The goal is to reorder the list such that the nodes are arranged as follows: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …, without modifying the values of the nodes. Only the structure of the list can be changed.
Problem
Approach
Steps
Complexity
Input: The input consists of a singly linked list with integer values. The linked list is given by its head node.
Example: Input: head = [10, 20, 30, 40]
Constraints:
• The number of nodes in the list is in the range [1, 5 * 10^4].
• 1 <= Node.val <= 1000
Output: The output should be the reordered linked list where nodes are arranged as L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...
Example: Output: [10, 40, 20, 30]
Constraints:
• The output should be a singly linked list with the nodes rearranged as described.
Goal: The goal is to reorder the linked list as per the given structure without modifying the node values.
Steps:
• 1. Find the middle of the list using the slow and fast pointer approach.
• 2. Reverse the second half of the list.
• 3. Merge the first half and the reversed second half by alternating nodes from each half.
Goal: The solution must operate within the given constraints and reorder the list in linear time.
Steps:
• The list must be reordered in O(n) time and O(1) extra space.
Assumptions:
• The input list is non-empty and contains valid integers.
• The list is not cyclic.
• Input: Input: head = [10, 20, 30, 40]
• Explanation: In this example, the list is reordered as [10, 40, 20, 30], where the first node is followed by the last node, then the second node, followed by the second last node, and so on.
Approach: The solution involves three main steps: finding the middle of the list, reversing the second half, and merging the two halves.
Observations:
• The problem requires rearranging nodes without modifying their values.
• A two-pointer approach can help find the middle of the list. After that, reversing the second half allows us to merge both halves in the required order.
Steps:
• 1. Use two pointers (slow and fast) to find the middle of the list.
• 2. Reverse the second half of the list starting from the node after the middle.
• 3. Merge the two halves by alternately linking nodes from each half.
Empty Inputs:
• If the input list contains only one node, the list remains unchanged.
Large Inputs:
• The algorithm should efficiently handle lists with up to 50,000 nodes.
Special Values:
• The list may contain nodes with varying values, but the algorithm should not modify their values, only their positions.
Constraints:
• The solution must use linear time and constant space.
This defines the `reorderList` function, which reorders the nodes of a linked list in a specific pattern by modifying the list in-place.
2 : Pointer Initialization
ListNode* fast = head, *slow = head;
Two pointers, `fast` and `slow`, are initialized at the head of the list. `fast` moves two steps at a time, and `slow` moves one step at a time.
3 : Find Middle
while(fast->next && fast->next->next) {
This loop runs until the `fast` pointer reaches the end of the list. It helps in finding the middle of the linked list using the slow and fast pointer technique.
4 : Move Slow Pointer
slow = slow->next;
The `slow` pointer moves one step at a time toward the middle of the list.
5 : Move Fast Pointer
fast = fast->next->next;
The `fast` pointer moves two steps at a time, so when it reaches the end, the `slow` pointer will be at the middle of the list.
6 : Middle Node
ListNode* mid = slow->next;
After finding the middle of the list, the `mid` pointer is initialized to the node right after the `slow` pointer.
7 : Break First Half
slow->next =NULL;
Breaks the list into two halves by setting `slow->next` to `NULL`, thus isolating the first half of the list.
8 : Pointer Initialization for Reversal
ListNode* next, *prev =NULL;
Two pointers, `prev` and `next`, are initialized. `prev` is used for reversing the second half of the list.
9 : Reverse Second Half
while(mid) {
This loop reverses the second half of the list by iterating over the nodes starting from `mid`.
10 : Save Next Node
next = mid->next;
Saves the next node in the `next` pointer to avoid losing the reference during the reversal.
11 : Reverse Link
mid->next = prev;
Reverses the `mid` node's `next` pointer to point to the previous node, effectively reversing the list.
12 : Update Previous Pointer
prev = mid;
Moves the `prev` pointer one step forward to the current node (`mid`), preparing it for the next iteration.
13 : Move Mid Pointer
mid = next;
Moves the `mid` pointer to the next node in the original list.
14 : Pointer Initialization for Merging
ListNode* l1 = head, *l2 = prev;
Initializes two pointers, `l1` pointing to the head of the first half, and `l2` pointing to the head of the reversed second half.
15 : Merge Two Halves
while(l1 && l2) {
This loop merges the two halves by alternating nodes from `l1` and `l2`.
16 : Save Next Node in First Half
ListNode* tmp1 = l1->next;
Saves the next node of `l1` in `tmp1` to prevent losing the reference during the merge.
17 : Connect First Half to Second Half
l1->next = l2;
Connects the current node of the first half (`l1`) to the current node of the second half (`l2`).
18 : Save Next Node in Second Half
ListNode* tmp2 = l2->next;
Saves the next node of `l2` in `tmp2` to ensure the merge can continue.
19 : Connect Second Half to First Half
l2->next = tmp1;
Connects the current node of the second half (`l2`) to the next node of the first half (`tmp1`).
20 : Move to Next Nodes
l1 = tmp1;
Moves the `l1` pointer to the next node in the first half.
21 : Move to Next Nodes
l2 = tmp2;
Moves the `l2` pointer to the next node in the second half.
Best Case: O(n), when the list is reordered by following the standard procedure.
Average Case: O(n), the list will always require a full traversal for reordering.
Worst Case: O(n), the solution works in linear time in all cases.
Description: The time complexity is O(n) because we traverse the list multiple times, but each traversal is linear.
Best Case: O(1), the space complexity remains constant.
Worst Case: O(1), since only a few pointers are used.
Description: The space complexity is O(1) because no extra space is used apart from a few pointers.
