143. Reorder List

 1# Definition for singly-linked list.
 2# class ListNode:
 3#     def __init__(self, val=0, next=None):
 4#         self.val = val
 5#         self.next = next
 6class Solution:
 7    def reorderList(self, head: Optional[ListNode]) -> None:
 8        """
 9        Do not return anything, modify head in-place instead.
10        """
11        og_head = head
12
13        slow, fast = head, head
14        while fast and fast.next:
15            slow = slow.next
16            fast = fast.next.next
17
18        # we will reverse the second half (ref: 206. Reverse Linked List)
19        curr = slow.next  # beginning of the second half
20        prev = slow.next = None
21
22        while curr:
23            nxt = curr.next
24            curr.next = prev
25            prev = curr
26            curr = nxt
27
28        head2 = prev  # reversed second half's head
29
30        while head and head2:
31            nxt = head.next
32            nxt2 = head2.next
33            head.next = head2
34            head2.next = nxt
35            head = nxt
36            head2 = nxt2
37
38        return og_head