题解 | #重排链表#

from pickle import NEXT_BUFFER

class Solution:
    def reorderList(self, head):
		#Fast & Slow pointers
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        #if empty
        if not slow:
            return

        middle = slow.next
        slow.next = None

        #reverse middle to rev
        rev = None
        while middle:
            next_n = middle.next
            middle.next = rev
            rev = middle
            middle = next_n
        
        cur = head
        while rev:
            next_n = cur.next
            cur.next = rev
            rev = next_n
            cur = cur.next