专栏首页全部文章Day55:链表中环的入口结点

Day55:链表中环的入口结点

剑指Offer_编程题——链表中环的入口结点

题目描述:

给一个链表,若其中包含环,请找出该链表的环入口节点,否则,输出null。

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体实现:

链表中有环证明   首先在做题之前我们要证明一个链表是否存在环,这里我们用到的就是——快慢指针法。首先给大家介绍两个快慢指针的结论: 1、设置快慢指针,假如有环,他们最后一定相遇。 2、两个指针分别从链表头和相遇点继续出发,每次走一步,最后一定相遇与环入口。   接下来我们分别证明结论1、2。 一、首先让我们证明结论1:   我们首先设置快慢指针分别为fast和slow;fast每次走两步,low每次走一步,假如有环两者一定相遇。因为low一旦进环,可以看作fast在后面追赶low的过程,每次两者都接近一次,最后一定能追上。 这个过程类似于链表中倒数第K个结点中思路三的做法。因此,我们结论一就已经证明完毕了。 二、结论2的证明:   首先我们画一个带环的示意图,如下图所示:

   **证明:**假设x为环前面的路程(黑色路程),a为环入口到相遇点的路程(蓝色路程,假设顺时针走), c为环的长度(蓝色+橙色路程)。当快慢指针相遇的时候:此时慢指针走的路程为:Sslow = x + m * c + a ①; 快指针走的路程为: Sfast = x + n * c + a ② 即:2 Sslow = Sfast ③ 2 * ( x + mc + a ) = (x + n c + a) ④ 根据①②③④式可得:x = (n - 2 * m )c - a= (n - 2 m -1 )c + c - a,我们解释这个等式即:环前面的路程 = 数个环的长度(这里要让他等于0) + c - a;那么有一个问题:什么是c-a呢?其实从图中可以看出:这是相遇点后,环后面部分的路程。(橙色路程)。因此,我们可以让一个指针从起点A开始走,让一个指针从相遇点B开始继续往后走,2个指针速度一样,那么,当从原点的指针走到环入口点的时候(此时刚好走了x),那么没有经过一个环,说明等式相等。从相遇点开始走的那个指针也一定刚好到达环入口点。因此当二者会相遇,且恰好相遇在环的入口点。这个结论证明完毕。 思路一:   这两个结论就意味着有两种解法。首先我们看结论一的解法。即:直接判断链表中是否有环,然后得到环中节点的数目,最后就是在环中找到入口节点,具体我们用java将其实现。

public class Solution{
	public ListNode EntryNodeOfLoop(ListNode pHead){
		if(pHead == null)
			return null;
		ListNode s = pHead, r = pHead;
		boolean flag = false;
		while(r != null && r.next != null){
			s = s.next;
			r = r.next.next;
			if(s == r){
				flag = true;
				break;
			}
		}
		if(!flag){
			return null;
		}else{
			int n = 1;
			r = r.next;
			while(s != r){
				r = r.next;
				n++;
			}
			s = r = pHead;
			for(int i = 0; i < n; i++){
				r = r.next;
			}
			while(s != r){
				s = s.next;
				r = r.next;
			}
			return s;
		}
	}
}

代码效果图如图所示:

  如果在牛客网中,此代码可以通过,因为在牛客网中已经为我们定义了链表结构,具体定义如图所示:

  但是在本地编译器中我们还需要定义链表结构才能正常运行,具体用Java定义链表结构实现如下:

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

  我们要在本地测试代码的正确性还得加上main(),具体用Java实现如下:

public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode listNode=new ListNode(1);
		listNode.next=new ListNode(2);
		listNode.next=new ListNode(3);
		listNode.next=new ListNode(4);
		listNode.next=new ListNode(5);
		System.out.println(EntryNodeOfLoop(listNode));
	}

  该代码测试的效果如图所示:

思路二:   根据我们已经证明了的结论二,我们可以让fast一次走2步,slow一次走一步,如果该链表有环,两个指针必然在环内相遇,此时只需要把其中的一个指针重新指向链表头部,另一个不变(还在环内的相遇点),这次两个指针继续走,一次走一步,相遇的地方就是入口节点。具体我们用java和python两种语言将其实现。 1、首先我们用java将其实现:

public class Solution{
	public ListNode EntryNodeOfLoop(ListNode pHead){
		ListNode fast = pHead, slow = pHead;
		while(fast != null && fast.next != null){
			fast = fast.next.next;
			slow = slow.next;
			if(slow == fast)
				break;
		}
		if(fast == null || fast.next == null)
			return null;
		fast = pHead;
		while (fast  != slow){
			slow = slow.next;
			fast = fast.next;
		}
		return fast;
	}
}

代码效果图如图所示:

该代码测试的效果如图所示:

2、接下来我们用python将其实现:

class Solution:
	def EntryNodeOfLoop(self, pHead):
		if not pHead:
			return None
		fast = slow = pHead
		a = []
		while fast.next and fast.next.next:
			fast = fast.next.next
			slow = slow.next
			if fast.val == slow.val:
				initial = pHead
				while slow != initial:
					slow = slow.next
					initial = initial.next
				return slow
		return None

代码效果图如图所示:

  但是在本地编译器中我们还需要定义链表结构才能正常运行,具体用python定义链表结构实现如下:

class ListNode:
	def __init__(self, x):
		self.val = x
		self.next = None

思路三:   以上的思路一和思路二是最经典的解法,我们必须掌握,除此之外,我们还有其他的解法,可以利用一个辅助HashMap来解决该题,具体用java实现如下:

import java.util.HashMap;
public class Solution{
	public ListNode EntryNodeOfLoop(ListNode pHead){
		HashMap<ListNode, Integer> first = new HashMap<>();
		ListNode pListNode = pHead;
		while(pListNode != null){
			if(!first.containsKey(pListNode))
				first.put(pListNode, 1);
			else{
				if(pListNode.next == null)
					return null;
				return pListNode;
			}
			pListNode = pListNode.next;
		}
			return null;
	}
}

代码效果图如图所示:

该代码测试的效果如图所示:

思路四:   当然,我们也可以用一种简单、粗暴的做法,不过这种做法是很耗空间的。接下来我们用python实现该思路:

class Solution:
	def EntryNodeOfLoop(self, pHead):
		if not pHead:
			return None
		cur = pHead
		a = []
		while cur:
			a.append(cur)
			cur = cur.next
			if not cur:
				return None 
			if cur in a:
				return cur

代码效果图如图所示:

总结

  本题主要考察大家对链表中环的掌握情况以及找到环的入口节点,本文在解题之前首先给大家介绍如何证明在来链表中有环,并且给出了两个结论以及将其证明。在解答本题中,本文给出了四种解题思路,其中包括两个结论就有对应的两种解题思路,并且在第二种解题思路中,我们分别给出了java和python两种解题过程。另外,我们又给出了利用辅助的HashMap来解决该题以及最后一种就是一种暴力的解法,其最大的缺点就是占用大量的空间,并且虽然最后一种牛客网也可以通过,但是这种解法并不是本题考查的本意。其实我们最好掌握思路一和思路二的解法,这才是文章所考察的核心知识。因此,我们在做题的时候,应该多次尝试各种方法,扩展自己的思维,写出优质的代码。总之,我们要继续加油,争取早日找到工作,Good Luck!!!

参考文献

[1] bo.qiu_xbw [2] 白马长枪儒雅将 [3] 冰河入梦

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day56:删除链表中重复的结点

    思路一:   由于本题明确说明是已经排好序的链表,因此我们创建一个新的节点为了防止第一是重复的元素并且连上原来的链表,遍历原来的元素进行删除。如果有重复的那么...

    stefan666
  • Day14:链表中倒数第k个结点

    思路一:   我们需要遍历出链表的长度,然后遍历出我们需要的倒数第k个结点,这是我们常规的想法,当然也考虑了代码的鲁棒性和空指针,k为0,k应该大于链表的长度...

    stefan666
  • Day15:反转链表

    背景知识介绍   在做本题之前首先介绍一下链表的基本知识。在维基百科中,链表 是这样定义的:链表(Linked list)是一种常见的基础数据结构,是一种线...

    stefan666
  • 单链表

    单向链表(又名单链表、线性链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过从头部开始,依序往下读取。

    王小明_HIT
  • 链表问题-LeetCode 206、234、160(反转,回文,公共结点)

    示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

    算法工程师之路
  • leetcode445. Add Two Numbers II

    链表形式跟非链表形式的最大区别在于我们无法根据下标来访问对应下标的元素。假如我们希望从后往前对每个位置求和,则必须每次都从前往后访问到对应下标的值才可以。因此这...

    眯眯眼的猫头鹰
  • 删除链表的倒数第N个节点

    宇宙之一粟
  • leetcode链表之反转链表

    这里使用了current、previous、next来保存,初始化的时候previous及next都设置为null

    codecraft
  • leetcode链表之反转链表

    这里使用了current、previous、next来保存,初始化的时候previous及next都设置为null

    codecraft
  • 【CPP】《程序员面试金典》习题(2)——链表

    这次的题比较少,题目的主题是链表,最值得注意的是快慢指针的用法和最后一题的Floyd判圈算法。

    ZifengHuang

扫码关注云+社区

领取腾讯云代金券