Reorder List (Leetcode #143)
LeetCode's problem 143, "Reorder List," is a challenging yet rewarding question. Here, I'll walk you through the problem, a common brute force solution, and then guide you to the efficient solution using the attached code, helping you understand how to reorder a linked list step by step.
Understanding the Problem Statement
The task requires us to reorder a given singly linked list, defined as:
Given the head of a singly linked list, modify it in such a way that the nodes are reordered from their original sequence in the pattern: first node, last node, second node, second last node, and so on.
Specifically, given a list like
1 -> 2 -> 3 -> 4 -> 5
, the reordered list should be1 -> 5 -> 2 -> 4 -> 3
.
The aim is to do this in-place without altering the node values or using extra memory in the form of a new list.
Brute Force Approach
The brute force approach to solve this problem involves copying all the elements of the linked list to an array or a list, rearranging the values in the desired order, and then repopulating the original linked list. Though straightforward, this approach violates the in-place requirement of the problem and requires O(n) additional space.
Steps: Traverse the linked list and store its nodes in an array. Then, using two pointers, reorder them into the specified pattern and rebuild the linked list accordingly.
Time Complexity: This approach takes O(n) for the traversal and reordering but also uses O(n) space, which is not ideal.
Hint to Solve the Problem Efficiently
Instead of storing nodes in a list, think of breaking down the list in two parts, reversing one half, and then merging them back. Imagine the process as finding the middle point of the list and strategically reordering.
Efficient Solution
The attached code uses a three-step approach to solve the problem efficiently while ensuring we keep the space complexity at O(1). Here is a breakdown:
Find the Middle of the Linked List
We use two pointers,
slow
andfast
, to find the middle node of the list. Thefast
pointer moves twice as fast as theslow
pointer, meaning by the timefast
reaches the end of the list,slow
will be at the middle. This gives us the split point to divide the list into two halves.slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next
Reverse the Second Half of the List
The next step involves reversing the second half of the list, starting from the node
slow
. We use three pointers:previous
,current
, andnext_temp
to reverse the nodes iteratively until we reach the end of the list.previous, current = None, slow while current: next_temp = current.next current.next = previous previous = current current = next_temp
At the end of this step,
previous
will point to the new head of the reversed second half.Merge the Two Halves
Finally, we merge the two halves together. We use two pointers,
first
andsecond
, representing the first and second halves respectively. We alternate linking nodes from each half, ensuring the new reordered structure is achieved.first, second = head, previous while second.next: temp1, temp2 = first.next, second.next first.next = second second.next = temp1 first, second = temp1, temp2
Time and Space Complexity
Time Complexity: The solution takes O(n) time since each of the three main steps (finding the middle, reversing the second half, and merging) involves a linear traversal of the linked list.
Space Complexity: The solution operates with O(1) additional space, making it an in-place solution that satisfies the problem's constraints.
Conclusion
The problem requires us to reorder a singly linked list in a particular pattern, and while a brute force approach may seem feasible, the efficient method involves using pointer manipulation to achieve an in-place solution. By dividing, reversing, and merging the list, we achieve the desired outcome effectively with a linear time complexity and constant space complexity.