“双指针法”在单链表中的应用

78 阅读 0 评论 52 点赞

我是靠谱客的博主自信蛋挞，最近开发中收集的这篇文章主要介绍“双指针法”在单链表中的应用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在有关单链表的问题中，不可避免的就是容易丢失头指针

比如当前链表为1->2->3，头结点为1，如果不当使用head = head.next;就会造成头指针的丢失

由于这一特性，所以在链表问题中，我们可以通过双指针来解决问题

通过双指针的位置差来，来解决我们所需要解决的问题

1、环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

首先大概解释一下这题的含义，什么是环形链表？就是链表的尾部指向链表其中的一个节点，你永远遍历不完这个链表，因为链表会不断的循环

本题中这个pos是没有用的，它只起一个解释的作用

现在我们思考一个问题，我们想判断这个链表是不是环形链表，首先我们需要遍历这个链表

while(head != null && head.next != null){
head = head.next
}

如果这个链表是环形链表，那这个循环应该不会终止，会一直执行下去，造成死循环

这题有好几种解决方案，比如你可以使用Hashset来将每一个节点放进去，如果发现重复的就说明存在环

这种方法远远不如双指针法来的高效

双指针法解决环形链表

class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}

首先，我们构建两个指针一个是快指针fast，一个是慢指针slow，定义快指针每次走2格，慢指针每次走1格

ListNode fast = head;
ListNode slow = head;

我们不妨想象一下

①如果链表不存在环，链表的最后一个节点为NULL

因为快指针比慢指针走得快，在快指针走到链表末尾为空的时候，它就会停止

②如果链表存在环

因为链表存在环，所有两个指针永远都不会停止，会一直在跑

但是因为每次快指针走的都比慢指针快，就像跑1000米一样，你的对手跑的比你足够的快，他总会在某个时间点上超越你一圈

所以，快指针在有环的情况下肯定会遇到慢指针

那么我们就得出结论了

如果快指针停止了，代表没有环，如果快指针和慢指针相遇了则代表有环

完整代码如下：

 public boolean hasCycle(ListNode head) {
if (head == null){
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
return true;
}
}
return false;
}

读以可以去Leetcode141题环形链表尝试一下

2、删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

这题同样的也可以使用双指针法来解决，和上面一题不同的是，在这里我们不设置快指针和慢指针，我们设置左指针和右指针

这题的主要难点也就在于，只使用一趟扫描完成删除操作

首先，我们思考一个问题，就按照例题里面的例子，在1->2->3->4->5中删除倒数第2个节点

我们所希望的操作当然是可以直接让 3.next = 5;这样我们就完成了我们的删除操作，但是如何让3.next = 5出现就成了我们目前要解决的问题

我们观察一下这个问题，因为3和5之间的差值正好是2，也就是说，如果我们可以设置在访问到5的同时，同时访问到3,就可以实现在一趟扫描的情况下完成删除操作，（访问到5代表这个链表扫描完毕，访问到3代表着可以完成删除操作）

我们再举一个例子，在1->2->3->4->5中删除倒数第3个节点

倒数第三个节点为3，我们希望完成2.next = 4的操作，而且同样2和5之间相差3个节点，也就是需要删除的下一节点和末尾节点相差n个

我们再再再举一个例子 1->2->3 删除倒数第三个节点

这个例子就和上面的例子不同，我们要删除头节点，我们假设这个链表在1前面还有一个节点0

也就是说0->1->2->3,只要完成0.next = 2即可，0和3直接也相差n（n = 3）个节点。当然具体处理方法不是加个节点，这里只是一个举例

得出结论

现在，我们不难明白，我们只需要设置两个指针，让这两个指针直接相差n，就可以在同时访问到末尾时，同时获取到被删除节点的前一个节点了

代码举例

 public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode right = head;
ListNode left = head;
for (int i = 0; i < n; i++) {
right = right.next;
}
if (right == null) {
head = head.next;
return head;
}
while (right.next != null) {
left = left.next;
right = right.next;
}
left.next = left.next.next;
return head;
}