Reorder List
Examples
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]
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]
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.
1 <= Length of the list <= 1000.1 <= Node.val <= 1000Find the middle of the list with slow/fast pointers, then reverse the second half. Finally, merge the two halves by alternating nodes from the first and reversed second half. This works for both even and odd lengths, and leaves single-node or two-node lists unchanged.
Splitting at the middle separates the list into the correct front and back portions. Reversing the second half makes its nodes appear in the required order (`n-1, n-2, ...)). Alternating nodes from the two halves produces exactly the target interleaving without changing node values.
O(n)O(1)class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if not head or not head.next:
return
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
prev = None
curr = second
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
second = prev
first = head
while second:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2