题解 | #链表内指定区间反转 详细实现每一步 有图有真相#

链表内指定区间反转

https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        def reverse(head: ListNode) -> ListNode:
            prev = None
            curr = head
            while curr:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev
            
        # dummy处理边界情况,{5},1,1   {3,5},1,2
        dummy = ListNode(-1)
        dummy.next = head
        preList = dummy

        # 找到截取起点的前一个节点
        for _ in range(m - 1):
            preList = preList.next

        # 获得截取起点和截取终点
        cut_pre = preList.next
        cut_tail = cut_pre
        for _ in range(n - m):
            cut_tail = cut_tail.next

        # 断开截取部分与前后的连接
        preList.next = None
        tailList = cut_tail.next
        cut_tail.next = None

        # 反转截取部分的链表
        cut_pre_reversed = reverse(cut_pre)

        # 拼接反转后的链表
        preList.next = cut_pre_reversed
        cut_pre.next = tailList

        return dummy.next

dummy: 处理边界情况

preList: 截取起点的前一个节点

tailList: 截取终点的后一个节点

cut_pre:cut_tail : 截取部分

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务