剑指 offer之链表中环的入口结点_Java

2019/7/24 12:29:19 人评论 次浏览 分类:学习教程

题目:链表中环的入口结点
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

解题思路:
ps: 来自剑指 offer评论区
在这里插入图片描述

假设x为环前面的路程(黑色路程),a为环入口到相遇点的路程(蓝色路程,假设顺时针走), c为环的长度(蓝色+橙色路程)
当快慢指针相遇的时候:
此时慢指针走的路程为Sslow = x + m * c + a
快指针走的路程为Sfast = x + n * c + a
2 Sslow = Sfast
2 * ( x + m*c + 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)
从相遇点开始走的那个指针也一定刚好到达环入口点。
所以2者会相遇,且恰好相遇在环的入口点。
最后,判断是否有环,且找环的算法复杂度为:
时间复杂度:O(n)
空间复杂度:O(1)

代码实现:

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

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

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead){
        //定义两个快慢指针
		ListNode slow=pHead;
		ListNode fast=pHead;
		//快指针一次走两步,满指针一次走一步,找到两个链表的相遇节点
		while(fast!=null && fast.next!=null) {
			slow=slow.next;
			fast=fast.next.next;
			//两者的相遇点
			if(slow==fast) {
				//使快慢指针中的其中一个头节点
				fast=pHead;
				//找到换的入口节点
				while(slow!=pHead) {
					slow=slow.next;
					pHead=pHead.next;
				}
				return slow;
			}
		}
		//没有相遇节点,即没有环,返回null
		return null;
    }
}

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->