143. Reorder List
Medium
You are given the head of a singly linked-list. The list can be represented as:
Reorder the list to be on the following form:
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Example 2:
Constraints:
- The number of nodes in the list is in the range [1, 5 * 104].
- 1 <= Node.val <= 1000
Solution
class Solution:
def reorderList(self, head: ListNode) -> None:
def splitAtMid(head: ListNode):
prev = None
slow = head
fast = head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
return slow
def reverse(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
def merge(l1: ListNode, l2: ListNode) -> None:
while l2:
next = l1.next
l1.next = l2
l1 = l2
l2 = next
if not head or not head.next:
return
mid = splitAtMid(head)
reversed = reverse(mid)
merge(head, reversed)