leetcode刷题_PYTHON(15):链表(15) 重排链表

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        ##翻转函数
        def reverseList(node: ListNode):
            pre = None
            cur = node
            while cur:
                temp = cur.next   
                cur.next = pre
                pre = cur
                cur = temp
            return pre
        
        #快慢指针找中点
        slow=head
        fast=head
        while fast.next and fast.next.next:
            slow,fast=slow.next,fast.next.next
        
        #右半部分right逆序，左半部分left不动
        reverse_node=slow.next
        right=reverseList(reverse_node)
        slow.next=None
        left=head
        
        #左右两部分逐个拼接+
        while right:
            left=left.next
            head.next=right
            head=head.next
            right=right.next
            head.next=left
            head=head.next

作者：wantingchi
链接：https://leetcode-cn.com/problems/reorder-list/solution/ti-jie-qing-xi-zhi-xing-yong-shi-zai-suo-mhip/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。