题解 | #链表内指定区间反转#

链表内指定区间反转

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

BM2 链表内指定区间反转

解题思路:[头插法]

在学会了BM1.反转链表之后,要解决这个问题就很简单了,前一题是整个链表反转,这一题是部分反转,这上一题就是这道题的前置问题啊。那我们肯定是要先找到了第m个位置才能开始反转链表,而反转的部分就是从第m个位置到第n个位置,反转这部分的时候就参照BM1.反转链表

具体做法:

  • step 1:我们可以在链表前加一个表头,后续返回时去掉就好了,因为如果要从链表头的位置开始反转,在多了一个表头的情况下就能保证第一个节点永远不会反转,不会到后面去。
  • step 2:使用两个指针,一个指向当前节点,一个指向前序节点。
  • step 3:依次遍历链表,到第m个的位置。
  • step 4:对于从m到n这些个位置的节点,依次断掉指向后续的指针,反转指针方向。
  • step 5:返回时去掉我们添加的表头。

# 从m反转到n,-1->1->2->3->4->5,m=2,n=4
for i in range(m,n):
    temp = cur.next #第一次循环 pre:1 cur:2 temp:3
    cur.next = temp.next # 2->4  !!!赋值号左边代表指针的指向,右边代表指针所指的元素。比如temp:3 temp.next:4, cur.next代表2->3的指向。
    temp.next = pre.next # 3->2
    pre.next = temp # 1->3
   	# 第一次循环结束后变成-1->1->3->2->4->5

Code

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # 加个表头 -1->1->2->3->4->5
        res = ListNode(-1)
        res.next = head
        # 前序节点
        pre = res
        # 当前节点
        cur = head
        # 找到m
        for i in range(1,m):
            pre = cur
            cur = cur.next
        # 从m反转到n,-1->1->2->3->4->5,m=2,n=4
        for i in range(m,n):
            temp = cur.next #第一次循环 pre:1 cur:2 temp:3
            cur.next = temp.next # 2->4  !!!赋值号左边代表指针的指向,右边代表指针所指的元素。比如temp:3 temp.next:4, cur.next代表2->3的指向。
            temp.next = pre.next # 3->2
            pre.next = temp # 1->3
        # 返回去掉表头
        return res.next

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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