143. Reorder List

Description:

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
'''
[1] half-reversed)

idea::
reverse right-side of linked list
and link newly by two-pointer technique

code::
(below)

-T/C: O(n)
-S/C: O(1)
'''

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        slow,fast=head,head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next

        fast=self.reverse(slow)
        slow=head
        while slow.next!=fast and slow!=fast:
            slow_next=slow.next
            fast_next=fast.next
            slow.next=fast
            fast.next=slow_next
            slow=slow_next
            fast=fast_next

    
    def reverse(self,slow):
        prev=None
        cur=slow
        while cur:
            nex=cur.next
            cur.next=prev
            prev=cur
            cur=nex
        return prev