以下文章来源于一个搬砖的胖子 ,作者一个搬砖的胖子
微软工程师,正致力于打造互联网大厂面试题库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/
题目分析
对于链表题,光靠脑子想容易乱,一定要画图
其实这道题,就是两步骤:
待反转的区间内两两一翻转
然后进行连接,让 left 的前置节点指向 right ,left 节点指向 right 的后置节点。
整体思路就是这样,接下来就是边界问题。
由于我们会用到 left 的前置节点,
如果 left 为 1 ,left 是没有前置节点的,
为了减少特殊判断,我们引入虚拟头节点,
这样,哪怕题目要求反转整个 1->2->3->4->5,我们也能用上面的步骤的做。
解决完边界问题,又有个新的问题,
想想步骤 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;
}
};
网友评论已有0条评论, 我也要评论