143. Reorder List
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:
-
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.
-
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.
-
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.
Solution Approach
The implementation of the solution can be outlined in the below steps corresponding to the intuition described earlier:
-
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 thefast
pointer advances two nodes at a time. When thefast
pointer either reaches the end of the list or the node before the end, theslow
pointer will be at the middle of the list. The loopwhile fast.next and fast.next.next:
ensures we stop at the correct position in the list. -
Reversing the Second Half: In order to reverse the second half of the list, we first set
slow.next
toNone
to mark the end of the first half of the list. We then use three pointer variables (cur
,pre
, andt
) to reverse the second half of the list.cur
starts at the first node of the second half, whilepre
is set toNone
to mark the new end of the list. We then iterate through the second half usingwhile cur:
, in each iteration, we temporarily store the next node usingt = cur.next
, point the current node topre
, and then movepre
andcur
forward. -
Merging the Two Halves: We now have two lists: the first half, starting at
head
, and the second half, starting atpre
, 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 loopwhile pre:
allows us to do just that. During each iteration, we store the next node ofpre
int
, then we linkpre
to the next of the current node in the first list (cur.next
). After updatingcur.next
topre
, we advancecur
andpre
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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, andfast
is at L1. - In the second step,
slow
is at L1, andfast
is at L3. - In the third step,
slow
is at L2, andfast
is at the end (null), soslow
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, andpre
isNone
.- We swap the next of
cur
(which is L4) to point topre
and advancepre
to be L3 andcur
to be L4. - Now
cur
is L4, and we point L4 to the newpre
(which is L3), makingpre
equal to L4 andcur
toNone
.
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 andpre
at L4. - Save the next of
head
(L1) and linkhead
topre
(L4). List after this step: L0 ā L4. - Advance
head
to saved next (L1) andpre
to next in the reversed list (L3). - Save next of
head
again (L2) and linkhead
topre
(L3). List after this step: L0 ā L4 ā L1 ā L3. - Advance
head
to saved next (L2), and sincepre
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
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:
-
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 inO(n/2)
wheren
is the number of nodes in the list. This simplifies toO(n)
. -
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 hasn/2
nodes, so the loop runs inO(n/2)
, which also simplifies toO(n)
. -
Merging Two Halves: The third
while
loop merges the two halves of the list. Since it processes each node exactly once, its time complexity isO(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:
-
Pointers: The algorithm uses a constant number of pointers (
fast
,slow
,cur
,pre
,t
) whose space usage does not depend on the input size. -
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.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
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 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 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