• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetcode刷题_PYTHON(9):链表(9)反转链表 II

开发技术 开发技术 4小时前 2次浏览

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

leetcode刷题_PYTHON(9):链表(9)反转链表 II

 

 leetcode刷题_PYTHON(9):链表(9)反转链表 II

 

 

 

根据上面的图示,这里说下其中涉及的参数,以及其中反转过程中的步骤:

其中涉及的参数

dummy_node:哑节点,减少判断;
pre:指向 left 的前一个节点,反转过程中不变;
cur:初始指向需要反转区域的第一个节点,也就是 left的位置;
nxt:指向 cur 的下一个节点,跟随 cur 变化。
其中反转过程中的步骤:

将 cur 的下一个节点指向nxt 的下一个节点;
将 nxt 的下一个节点指向 pre 的下一个节点;
将 pre 的下一个节点指向 nxt。
循环上面三个步骤,直至反转结束。
根据上面的步骤,实现的代码如下:

https://pic.leetcode-cn.com/1616067008-ygfgJz-0092-reverse-linked-list-ii.gif

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy_node = ListNode(-1)
        dummy_node.next = head
        
        # 令 pre 指向 left 位置的前一个节点
        pre = dummy_node
        for _ in range(left - 1):
            pre = pre.next
        
        cur = pre.next
        # 通过头插法,实现反转
        for _ in range(right - left):
            nxt = cur.next
            cur.next = nxt.next
            nxt.next = pre.next
            pre.next = nxt
                    
        return dummy_node.next

作者:yiluolion
链接:https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/tou-cha-fa-dong-tu-shi-jie-92-fan-zhuan-ukmv1/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

leetcode刷题_PYTHON(9):链表(9)反转链表 II

 


程序员灯塔
转载请注明原文链接:leetcode刷题_PYTHON(9):链表(9)反转链表 II
喜欢 (0)