对于单链表相关的问题,双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决:
总的来说,双指针技巧在解决单链表相关问题时非常实用,它能够高效地解决许多常见问题,包括合并、分解、寻找节点、判断是否存在环等等。而我们需要使用双指针解决的以上问题,则是先要学会以下问题的解题思路,一起看看。
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
提示:
[0, 104]
-105 <= Node.val <= 105
pos
为 -1
或者链表中的一个 有效索引 。利用快慢指针原理 一个指针走得快,另一个走得慢,如果有循环,快指针会在莫个时刻追上慢的指针
/** 自定义类
*
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
//判断是否有循环
public boolean hasCycle(ListNode head) {
//判断是否为空指针 解决特殊情况
if(head==null)return false;
//定义另一个指针
ListNode second=head.next;
//利用快慢指针原理 一个指针走得快,另一个走得慢,如果有循环,
//快指针会在莫个时刻追上慢的指针
while(head!=null && second!=null && second.next!=null){
head=head.next;
second=second.next.next;
//如果快指针追上慢指针,说明有循环
if(head==second){
return true;
}
}
//如果两个指针同时为空,说明没有循环
return false;
}
}
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos
是 -1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
如果有环,快指针走的距离是慢指针的两倍,设总距离为2x。快指针首次在链表尾连接到链表中的位置移动了2x,慢指针移动了x。快指针追上慢指针,快指针走的距离为2x+2/3k环;慢指针的距离为 x+1/3k环。设置起点到链表尾连接到链表中的位置距离为l,现在慢指针再跟快指针按同样的速度行走l,两指针就可以在链表尾连接到链表中的位置相遇。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//声明快慢指针
ListNode second=head;
ListNode first=head;
//判断是否有环
while(second!=null && second.next!=null){
first=first.next;
second=second.next.next;
if(first==second){
break;
}
}
//如果没有环,直接返回null
if(second==null || second.next==null){
return null;
}
//如果有环,快指针走的距离是慢指针的两倍,设总距离为2x。快指针首次在链表尾连接到链表中的位置移动了2x,慢指针移动了x。快指针追上慢指针,快指针走的距离为2x+2/3k环;慢指针的距离为 x+1/3k环。设置起点到链表尾连接到链表中的位置距离为l,现在慢指针再跟快指针按同样的速度行走l,两指针就可以在链表尾连接到链表中的位置相遇。
first=head;
while(first!=second){
first=first.next;
second=second.next;
}
return first;
}
}