Solution
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
fast = slow = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
cur = slow.next
slow.next = None
pre = None
while cur:
t = cur.next
cur.next = pre
pre, cur = cur, t
cur = head
while pre:
t = pre.next
pre.next = cur.next
cur.next = pre
cur, pre = pre.next, t
def printList(head):
arr = []
p = head
while p:
arr.append(str(p.val))
p = p.next
print(" ".join(arr))
if __name__ == "__main__":
# 1‑2‑3‑4‑5
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
sol = Solution()
sol.reorderList(n1)
printList(n1)