Reorder Linked List
Problem Statement
You are given the head of a singly linked-list.
The positions of a linked list of length = 7
for example, can intially be represented as:
[0, 1, 2, 3, 4, 5, 6]
Reorder the nodes of the linked list to be in the following order:
[0, 6, 1, 5, 2, 4, 3]
Notice that in the general case for a list of length = n
the nodes are reordered to be in the following order:
[0, n-1, 1, n-2, 2, n-3, ...]
You may not modify the values in the list’s nodes, but instead you must reorder the nodes themselves.
Example 1:
Input: head = [2,4,6,8]
Output: [2,8,4,6]
Example 2:
Input: head = [2,4,6,8,10]
Output: [2,10,4,8,6]
Constraints:
1 <= Length of the list <= 1000
.1 <= Node.val <= 1000
You should aim for a solution with O(n)
time and O(1)
space, where n
is the length of the given list.
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(1)
space, where n
is the length of the given list.
Hint 1
A brute force solution would be to store the node values of the list in an array, reorder the values, and create a new list. Can you think of a better way? Perhaps you can try reordering the nodes directly in place, avoiding the use of extra space.
Hint 2
For example, consider the list [1, 2, 3, 4, 5]
. To reorder the list, we connect the first and last nodes, then continue with the second and second-to-last nodes, and so on. Essentially, the list is split into two halves: the first half remains as is, and the second half is reversed and merged with the first half. For instance, [1, 2]
will merge with the reversed [5, 4, 3]
. Can you figure out a way to implement this reordering process? Maybe dividing the list into two halves could help.
Hint 3
We can divide the list into two halves using the fast and slow pointer approach, which helps identify the midpoint of the list. This allows us to split the list into two halves, with the heads labeled as l1
and l2
. Next, we reverse the second half (l2
). After these steps, we proceed to reorder the two lists by iterating through them node by node, updating the next pointers accordingly.
Solution
Brute Force
# Definition for singly-linked list.class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
def reorder_list(head: Optional[ListNode]) -> None: """Reorders the linked list in-place.""" if not head: return
nodes = [] curr = head while curr: nodes.append(curr) curr = curr.next
i, j = 0, len(nodes) - 1 while i < j: nodes[i].next = nodes[j] i += 1 if i >= j: break nodes[j].next = nodes[i] j -= 1
nodes[i].next = None
Time complexity: O(n)
Space complexity: O(n)