LeetCode--142. Linked List Cycle II

本文主要是介绍LeetCode--142. Linked List Cycle II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?

Analysis:
按I的思路，我们又慢指针S和快指针F。。。F走两步，S走一步。。。若有环，必定相遇。

F走的路程应该是S的两倍

S = x + y
F = x + y + z + y = x + 2y + z
2*S = F
2x+2y = x + 2y + z
得到x = z

也就是从head到环开始的路程＝从相遇到环开始的路程

那么。。。只要S和F相遇了，我们拿一个从头开始走，一个从相遇的地方开始走两个都走一步，那么再次相遇必定是环的开始节点。

 /** #->#->#->O->#->#->...->#*          ^             |*          |     环      |*          |             |*          #<-...<-*<-#<-*O为环的起点，*为快指针追上慢指针的节点*/

Answer:

/*** 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) {//判断链表节点数<=3的情况，因为后面的程序要求节点数大于等于3if(head==null || head.next==null) return null;if(head.next.next==null) {if(head==head.next.next) return head;else return null;}//定义快慢指针，如果存在环，结果会使快指针追上慢指针ListNode fast=head;ListNode slow=head;while(fast!=null && fast.next !=null ){fast = fast.next.next;slow = slow.next;if(fast==slow) break;}//如果while是因为遇到链表尾即没有环 则返回null；if(fast==null || fast.next ==null) return null;//如果有环则从head再次出发一个节点（速度和slow一样），//这个节点和slow相遇的节点即为环的开始点else{ListNode trird = head;while(trird!=slow){trird = trird.next;slow = slow.next;}return trird;}}
}