每天一算:Reverse Linked List II

LeetCode上第92号问题:反转链表II

题目

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4.    
输出: 1->4->3->2->5->NULL

解题思路

Reverse Linked List 的延伸题。

可以考虑取出需要反转的这一小段链表,反转完后再插入到原先的链表中。

以本题为例:

变换的是2,3,4这三个点,那么我们可以先取出2,用front指针指向2,然后当取出3的时候,我们把3加到2的前面,把front指针前移到3,依次类推,到4后停止,这样我们得到一个新链表4->3->2, front指针指向4。

对于原链表来说,有两个点的位置很重要,需要用指针记录下来,分别是1和5,把新链表插入的时候需要这两个点的位置。

  • 用pre指针记录1的位置

  • 当4结点被取走后,5的位置需要记下来

  • 这样我们就可以把倒置后的那一小段链表加入到原链表中

动画演示

动画演示GIF加载有点慢,请稍等片刻^_^

每天一算:Reverse Linked List II

参考代码

每天一算:Reverse Linked List II


每天一算:Reverse Linked List II

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 每天一算:Reverse Linked List II

我还会在以下平台发布内容

GitHub 哔哩哔哩