聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

别忽视它!

2022-02-18 10:46 浏览: 2576563 次 我要评论(0 条) 字号:

以下文章来源于一个搬砖的胖子 ,作者一个搬砖的胖子

一个搬砖的胖子 .

微软工程师,正致力于打造互联网大厂面试题库CodeTop

来自公众号:一个搬砖的胖子

前言

大家好,我是一个搬砖的胖子

反转链表是最常见的算法题,大家应该都掌握了。

然而,不少面试官开始避而不问,转而问进阶版的反转链表

例如,

  • 翻转单链表的区间 (2021.09 字节跳动)
  • 将链表的第m到第n个位置进行反转 (2021.08 猿辅导·后端·二面)
  • 算法题:指定区间链表反转 (2021.09 美团·后端·一面)

这道题其实是 Leetcode 的 92. 反转链表 II

它不在力扣官方的 HOT 100 中,但是非常容易考!

截止到今天,字节跳动已出现过 39 次,位列字节榜 Top 30;美团出现过 23 次,位列美团榜 Top 10;猿辅导出现过 12 次,位列猿辅导榜 Top 2 ...

这道题一定要引起大家的注意了!!

题目描述

给一个单链表,反转从位置 left 到位置 right 的节点,返回反转后的链表。

要求:一趟扫描完成反转。

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

题目来源链接:https://leetcode-cn.com/problems/reverse-linked-list-ii/

题目分析

对于链表题,光靠脑子想容易乱,一定要画图

其实这道题,就是两步骤:

  1. 待反转的区间内两两一翻转

  2. 然后进行连接,让 left 的前置节点指向 right ,left 节点指向 right 的后置节点

图 1

整体思路就是这样,接下来就是边界问题。

由于我们会用到 left 的前置节点,

如果 left 为 1 ,left 是没有前置节点的,

为了减少特殊判断,我们引入虚拟头节点

这样,哪怕题目要求反转整个 1->2->3->4->5,我们也能用上面的步骤的做。

图 2

解决完边界问题,又有个新的问题,

想想步骤 1 需要执行几次翻转操作?

举个例子数一下就是了,图 1 中 left = 2, right = 4, 一共反转了 2 次(图中一共 2 个红色指针),

因此,就有 步骤 1 需要执行 right - left 次反转操作。

凡是遇到这种需要计算的,我都会举个例子算一下,然后得到公式。

好了,保证思路清晰后,来看看代码吧~

参考代码

Python 版

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        p = dummy
        #p指向left的前置节点
        for i in range(left-1):
            p = p.next
        #步骤1:m,n用于区间内两两一翻转,执行right-left次
        m = p.next
        n = m.next
        for i in range(right-left):
            temp = n.next
            n.next = m
            m = n
            n = temp
        #步骤2:连接。注意顺序
        p.next.next = n
        p.next = m
        return dummy.next

C++ 版

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *p = dummy;
        //p指向left的前置节点
        for (int i = 0; i < left - 1; i ++ ) p = p->next;
        //步骤1:m,n用于区间内两两一翻转,执行right-left次
        ListNode *m = p->next, *n = m->next;
        for (int i = 0; i < right - left; i ++ )
        {
            ListNode *temp = n->next;
            n->next = m;
            m = n;
            n = temp;
        }
        //步骤2:连接。注意顺序
        p->next->next = n;
        p->next = m;
        return dummy->next;
    }
};



--- EOF ---


推荐↓↓↓


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复