题解 | #重排链表#

'''
1、先使用快慢指针遍历链表，当快指针下一次要到结尾时，慢指针在链表中点
2、此时慢指针指的即是链表的中点，也是我们重排序的终点，置空慢指针的下一个，并反转后面的链表
3、合并俩个链表 head,n_head
'''
class Solution:
    def reorderList(self, head):
        # write code here
        # 123456  162534
        if head==None or head.next==None or head.next.next==None:
            return head
        slow = head
        quick = head

        while quick.next is not None and quick.next.next is not None:
            slow = slow.next
            quick = quick.next.next
        # 慢指针刚好在中点
        # 反转后半部分
        n_head = slow.next
        slow.next = None
        n_head = self.resolve(n_head)
        
        while n_head is not None:
            temp = n_head.next
            n_head.next = head.next
            head.next = n_head
            head = n_head.next
            n_head = temp


    def resolve(self, head):
        if head is None:
            return head
        tail = head # 取出第一个
        head = head.next
        tail.next = None
        while head is not None:
            p_node = head.next
            head.next = tail
            tail = head
            head = p_node
        return tail