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

链表内指定区间反转

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 : 截取部分

全部评论

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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