アルゴリズムのチェーンテーブルループ検出
問題の説明
ループチェーンテーブルが与えられ、アルゴリズムがループの先頭ノードを返すことを実現する.ループチェーンテーブルの定義:チェーンテーブル内のノードのnext要素がその前に現れたノードを指し、チェーンテーブルにループがあることを示します.
例1:入力:head=[1,2,3,4]、pos=1出力:tail connects to node index 1説明:チェーンテーブルにループがあり、その末尾が2番目のノードに接続されている.
例2:入力:head=[5,3]、pos=0出力:tail connects to node index 0解釈:チェーンテーブルにリングがあり、その末尾が最初のノードに接続されている.
例3:入力:head=[3]、pos=-1出力:no cycle解釈:チェーンテーブルにリングがありません.
要求空間複雑度o(1)
アルゴリズム実装
ループチェーンテーブルが与えられ、アルゴリズムがループの先頭ノードを返すことを実現する.ループチェーンテーブルの定義:チェーンテーブル内のノードのnext要素がその前に現れたノードを指し、チェーンテーブルにループがあることを示します.
例1:入力:head=[1,2,3,4]、pos=1出力:tail connects to node index 1説明:チェーンテーブルにループがあり、その末尾が2番目のノードに接続されている.
例2:入力:head=[5,3]、pos=0出力:tail connects to node index 0解釈:チェーンテーブルにリングがあり、その末尾が最初のノードに接続されている.
例3:入力:head=[3]、pos=-1出力:no cycle解釈:チェーンテーブルにリングがありません.
要求空間複雑度o(1)
アルゴリズム実装
/**
* Definition for singly-linked list.
* 1. , (fast slow 2 )
* 2. fast head ,slow , , , “ ”
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow==fast){
break;
}
}
// NULL
if(fast==null||fast.next==null){
return null;
}
// ,
// ,
fast = head;
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}