链表内指定区域间反转
2022-03-04 / 2 min read
题目
这个问题较之前的链表反转,存在很多不同的地方,这里我们将详细的进行说明
思路总结
这个问题在面试中也是很容易考察的,我在书写的时候出现了思维上次的错误,查看了解析过后我发现了自己在这个问题上的不足。在这里一步一步的进行解析。
首先我们要明白我们做的这次反转,只是反转链表中的一部分,所以我们在交换位置位置的时候要格外的小心。
上面是我们准备的示意图,我们看到这里还没有发现与之前的链表反转有什么不同。
因为我们是需要交换其中的一部分,所以我们现在假设我们交换的是中间两个
在这里我们首先需要做的就是移动至相关位置。
现在我们移动到了想要的位置后,下一步就是进行交换,这里在交换的时候我们需要判断我们要交换多少次。答案是n右边界-m左边界次,这里我们要演示的是交换的核心过程
从图中我们看到我们首先做的是,将Next指针指向cur.Next,然后更具上面的步骤进行,我之前没有思考到位的就是pre指针的用法,最先我让他在交换的过程中也跟着交换,这是不对的。从图中我们知道他始终要指向交换后的对头上。
具体的实现代码如下: