# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
""" tc O(N) sc O(1)
Do not return anything, modify head in-place instead.
main idea: second half of LList reverse
zigzag insert into first half of LList
may discuss odd and even
1. loop to the end, cnt N --- \ fast slow ptr
2. reverse from tail, until N/2 --- /
3. start from head, zigzag in sert tail
"""
if not head or not head.next:
return
# step1: find middle point using fast slow ptr
# prev will be tail of 1st half while slow will be head of second half
slow, fast, prev = head, head, None
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
l1, l2 = head, self._reverse(slow)
self._merge(l1,l2)
# step2: reverse the 2nd half linked list
def _reverse(self,head):
prev,cur,nextt = None, head, None
while cur:
nextt = cur.next
cur.next = prev
prev = cur
cur = nextt
return prev
# step3: zigzag insert 2nd half into 1st half
def _merge(self, l1,l2):
while l1:
n1, n2 = l1.next, l2.next
l1.next = l2
if not n1:
break
l2.next = n1
l1, l2 = n1, n2