143. Reorder List

https://leetcode.com/problems/reorder-list/

Python

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head:
            return

        # Leetcode 876: Middle of Linked List
        left, right = head, head
        while right and right.next:
            left = left.next
            right = right.next.next

        # Leetcode 206: Reverse Linked List
        pre, cur = None, left
        while cur:
            cur.next, pre, cur = pre, cur, cur.next

        # Leetcode 21: Merge Two Sorted Linked Lists
        left, right = head, pre
        while right.next:
            left.next, left = right, left.next
            right.next, right = left, right.next