143.-reorder-list.md

143. Reorder List

• Medium

• 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.

Analysis

The solution uses 3 steps to solve this problem. The first part is to separate the linked list into two parts at the middle point. Then we reversed the second part of the linked list, which is step two. The last step is to interleaving merging the two lists.

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

            mid=slow.next
            slow.next=None 


            p,q,mid.next=mid,mid.next,None
            while q:
                p,q,p.next=q,q.next,p
            mid=p

            p,q=head,mid
            while q:
                pp,qq=p,q
                p,q=p.next,q.next
                pp.next,qq.next=qq,p