題目描述
輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。
image.png
代碼實(shí)現(xiàn)
思路一
開(kāi)始遍歷兩遍鏈表獲取兩個(gè)表的長(zhǎng)度炕泳，比較長(zhǎng)度讓長(zhǎng)的一個(gè)先走差值個(gè)步長(zhǎng)，
再兩個(gè)一起走上祈。（快慢指針?biāo)枷肱嘧瘢彩擎湵韱?wèn)題的一般性思路）
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null||pHead2==null)return null;
ListNode p = pHead1;
ListNode q = pHead2;
int length1 = getLength(p);
int length2 = getLength(q);
//如果鏈表1的長(zhǎng)度大于鏈表2的長(zhǎng)度
if(length1>=length2) {
int len = length1-length2;
//先遍歷鏈表1，遍歷的長(zhǎng)度就是兩鏈表的長(zhǎng)度差
while(len>0) {
p=p.next;
len--;
}
}else if(length1<length2) {
//如果鏈表2的長(zhǎng)度大于鏈表1的長(zhǎng)度
int len = length2-length1;
//先遍歷鏈表2登刺，遍歷的長(zhǎng)度就是兩鏈表的長(zhǎng)度差
while(len>0) {
q=q.next;
len--;
}
}
//開(kāi)始齊頭并進(jìn)籽腕，直到找到第一個(gè)公共結(jié)點(diǎn)
while(p!=q) {
p=p.next;
q=q.next;
}
return p;
}
//求指定鏈表的長(zhǎng)度
private int getLength(ListNode q) {
int length = 0;
ListNode current = q;
while(current!=null) {
length++;
current=current.next;
}
return length;
}
}
思路2
如果有公共節(jié)點(diǎn)，
- 若兩個(gè)鏈表長(zhǎng)度相等纸俭，那么遍歷一遍后皇耗，在某個(gè)時(shí)刻，p1 == p2
- 若兩個(gè)鏈表長(zhǎng)度不相等揍很，那么短的那個(gè)鏈表的指針pn
也就是p1或p2）
必先為null郎楼，那么這時(shí)再另pn
鏈表頭節(jié)點(diǎn)。經(jīng)過(guò)一段時(shí)間后窒悔，
則一定會(huì)出現(xiàn)p1 == p2呜袁。
如果沒(méi)有公共節(jié)點(diǎn)：這種情況可以看成是公共節(jié)點(diǎn)為null，顧不用再考慮简珠。
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null||pHead2==null)return null;
ListNode p = pHead1;
ListNode q = pHead2;
while(p!=q) {
if(p!=null) {
p=p.next;
}
if(q!=null) {
q=q.next;
}
if(p!=q) {
if(p==null) {
p=pHead1;
}
if(q==null) {
q=pHead2;
}
}
}
return p;
}
}
