链表遍历之双指针

最近在刷leetcode上的题目的时候,碰上了链表.其中有几个是关于在链表中查找环,此时有两种思路

一是使用哈希,这种思路比较简单,但是复杂较高,一般为O(n),并且还要额外的hash开销

二就是使用双指针.

使用快慢两个指针:一个一次跳一步,一个一次跳两步/如:

ListNode low,fast;

在有环的情况下,

可以在数学上证明,当两者出发后到第一次相遇,一定相差1个环

 如下:其中B为环入口,BCDEB即为一个环.D为第一次相遇的点.

下面实例:

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码:

import java.util.HashSet;
/**
*
*/
/**
* @author 作者
* @version 创建时间：2019年6月9日 下午1:23:11
* 类说明
*/
/**
* @author Administrator
*
*/
public class leetcode_142 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
}
//哈希法
public ListNode detectCycle(ListNode head) {
ListNode des = head;
HashSet<ListNode>tem = new HashSet<>();
while(des != null) {
if(!tem.contains(des)) {
tem.add(des);
}else {
return des;
}
des = des.next;
}
return null;
}
public ListNode detectCycle1(ListNode head) {
ListNode low = head;
ListNode fast = head;
//
HashSet<ListNode>low = new HashSet<>();
int flag = 0;
//使用这种的时候一定要一起跳,而不能将fast的第二跳放到后面
//
while(low != null) {
//
low = low.next;
//
fast = fast.next;
//
//
if(fast != null) {
//
fast = fast.next;
//
//
}else
//
return null;
//
//
if(fast==null || low==null)
//
return null;
//
//
if(fast == low) {
//
flag = 1;
//
break;
//
//
}
//
//
//
//
}
//下面这种更简洁
while(fast!=null && fast.next!=null) {
low = low.next;
fast = fast.next.next;
if(low==null || fast==null)
return null;
if(low == fast) {
flag = 1;
break;
}
}
if(flag == 1) {
//有环
fast = head;
while(fast != low) {
fast = fast.next;
low = low.next;
}
return fast;
}
else
return null;
}
static class ListNode{
int val;
ListNode next;
ListNode (int x){
this.val = x;
this.next = null;
}
}
}

最后

以上就是舒服雪糕为你收集整理的链表遍历之双指针的全部内容，希望文章能够帮你解决链表遍历之双指针所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。