題目描述： 求兩個連結清單的第一個公共節點
輸入兩個連結清單，找出它們的第一個公共節點。
如下面的兩個連結清單：
在節點 c1 開始相交。
題解一：
我們先來分析一下這個題目，求兩個連結清單的公共節點，對于這個問題我們一般都會設定兩個引用分别指向兩個連結清單頭，然後周遊連結清單直到相遇，但是什麼情況就能相遇呢？
由上圖所示，我們分别設A連結清單非公共部分的節點長度為a，B連結清單公共節點的長度是b，A、B連結清單公共部分為c.當引用cur1從A連結清單的頭節點開始向後走，引用cur2從B連結清單的頭節點開始向後走,直到走到末尾，發現此時cur1和cur2兩個引用調換指向連結清單頭部的位置時剛好到達第一個公共節點的路程是一樣的，即：
a+b+c=c+b+a
代碼：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(h1==null || h2==null)
{
return null;
}
ListNode h1=headA;
ListNode h2=headB;
while(h1!=h2)
{
if(h1==null)//走到末尾調換連結清單頭
{
h1=headB;
}else{
h1=h1.next;
}
if(h2==null)
{
h2=headA;
}else{
h2=h2.next;
}
}
return h2;
}
}
代碼跑過了，但是有沒有注意到，我們并沒有考慮到當兩條連結清單沒有相交的情況，是以，我們還需要改進一下。
思路：
用一個整型變量count來計數，每次連結清單頭由A變為B或者由B變為A，count++；當count=3時，就表示兩條連結清單沒有相交，直接跳出循環。
如果沒有這個判斷，兩條連結清單沒有相交的情況就會成為死循環。
更改後的代碼：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(h1==null || h2==null)
{
return null;
}
ListNode h1=headA;
ListNode h2=headB;
int count=0;
while(count<=2)
{
if(h1==null)//走到末尾調換連結清單頭
{
h1=headB;
count++;
}
if(h2==null)
{
h2=headA;
count++;
}
if(h1==h2){
return h1;
}
h1=h1.next;
h2=h2.next;
}
return null;
}
}
題解二： 另一種思路就是，先求出兩個連結清單節點的內插補點len，讓節點較長的連結清單先走len個節點，然後連個連結清單再一人一步向前走，直到相遇。
代碼：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null || headB==null)
{
return null;
}
ListNode cur1=headA;
ListNode cur2=headB;
int k1=0;
int k2=0;
boolean bol=true;//為true認為h1長;如果h2長後面代碼将bol置為false
while(cur1!=null ||cur2!=null)
{
if(cur1!=null)
{
k1++;
cur1=cur1.next;
}
if(cur2!=null)
{
k2++;
cur2=cur2.next;
if(cur1==null)//cur1為空，cur2不為空的時候表示連結清單B長，将bol置為false
{
bol=false;
}
}
}
int len=k1>k2?(k1-k2):(k2-k1);//長度內插補點
cur1=(bol==true?headA:headB);//存的是連結清單節點比較長的
cur2=(bol==true?headB:headA);
while(len>0)
{
cur1=cur1.next;
len--;
}
while(cur2!=cur1 && cur1!=null &&cur2!=null)
{
cur2=cur2.next;
cur1=cur1.next;
}
return cur1;
}
}