動機

沒想到可以用reverse!!

Problem

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.

 

Example 1:

Input: head = [1,2,3,4]Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]Output: [1,5,2,4,3]

 

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000

Sol

求中點之後有左右兩邊，就開始塞 不過因為右邊是反的，就用遞迴後半段去塞，不然就是reverse

class Solution:
    def getMid(self,h):
        n, e = h,h
        odd = False
        while e.next and e.next.next:
            n,e = n.next, e.next.next
        return [n, e.next is None]
    def reorderList(self, head: ListNode) -> None:
        mid, odd = self.getMid(head)
        right, leftEnd = (mid.next, mid) if odd else (mid.next,mid.next)
        
        def bt(now):
            nonlocal right
            if now is leftEnd:
                return
            else:
                bt(now.next)
                #print(now.val, right.val)
                nextRight, nextNow = right.next, now.next
                now.next, right.next = right, nextNow
                right = nextRight
        if leftEnd is not None:
            bt(head)
            leftEnd.next = None