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

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

 

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

 

 

解题思路

1、快慢指针找中点,等分成左右两个部分
2、右半部分逆序
3、左右两个部分逐个拼接

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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

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

上一篇:vendor/easywechat-composer/easywechat-composer/src:


下一篇:Dynamic 分派操作、共享记录