leetcode Linked List Cycle II
3543 ワード
タイトルリンク
思想:まず輪があるかどうかを判断する
ループがあれば、2つのリストの最初の共通ノードを探すことができます.この2つのチェーンテーブルはそれぞれhead->......->tailです
tail->….tail
思想:まず輪があるかどうかを判断する
ループがあれば、2つのリストの最初の共通ノードを探すことができます.この2つのチェーンテーブルはそれぞれhead->......->tailです
tail->….tail
/** * 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) {
if(head==null)
{
return null;
}
ListNode pre=head;
ListNode tail=head;
while(true)
{
if(pre!=null&&pre.next!=null)
{
pre=pre.next.next;
tail=tail.next;
}
else
{
break;
}
if(pre==tail)
{
return getIntersectionNode(pre,head);
}
}
return null;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode temp;
//
int linkALength=0;
temp=headA;
while(temp!=headA)
{
temp=temp.next;
linkALength++;
}
int linkBLength=0;
temp=headB;
while(temp!=headB)
{
temp=temp.next;
linkBLength++;
}
//
ListNode linkA=headA;
ListNode linkB=headB;
if(linkALength>linkBLength)
{
for(int i=0;i<linkALength-linkBLength;i++)
{
linkA=linkA.next;
}
}
else
{
for(int i=0;i<linkBLength-linkALength;i++)
{
linkB=linkB.next;
}
}
while(linkA!=null&&linkB!=null)
{
if(linkA==linkB)
{
return linkA;
}
linkA=linkA.next;
linkB=linkB.next;
}
return null;
}
}