聲明： 本總結(jié)僅為個(gè)人學(xué)習(xí)總結(jié)，以防止遺忘而作拇派，不得轉(zhuǎn)載和商用。
題目:給定兩個(gè)單向鏈表,計(jì)算兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn),若沒(méi)有公共節(jié)點(diǎn),返回空
令兩鏈表的長(zhǎng)度為m,n,不妨認(rèn)為m>=n,由于兩個(gè)鏈表從第一個(gè)公共結(jié)點(diǎn)到鏈表的尾結(jié)點(diǎn)是完全重合的.所以前面的(m-n)個(gè)結(jié)點(diǎn)一定沒(méi)有公共結(jié)點(diǎn)
算法:先分別遍歷兩個(gè)鏈表得到它們的長(zhǎng)度m,n.長(zhǎng)鏈表空轉(zhuǎn)(m-n)次,同步遍歷兩鏈表,直至找到相同結(jié)點(diǎn)或到鏈表結(jié)束
時(shí)間復(fù)雜度O(m+n)
Java版本實(shí)現(xiàn):
public static Node findFirstSameNode(Node pA, Node pB){
//因?yàn)橛蓄^指針,所以指向第一個(gè)有效結(jié)點(diǎn)
pA = pA.next;
pB = pB.next;
//計(jì)算兩個(gè)鏈表的長(zhǎng)度
int nA = calcLength(pA);
int nB = calcLength(pB);
if (nA > nB) {//保證后面nB-nA > 0
Node tempNode = pA;
pA = pB;
pB = tempNode;
int temp = nA;
nA = nB;
nB = temp;
}
//空轉(zhuǎn)nB-nA次
for(int i=0;i<nB-nA;i++){
pB = pB.next;
}
//齊頭并進(jìn)
while(pA != null){
if (pA.value == pB.value) {
return pA;
}
pA = pA.next;
pB = pB.next;
}
return null;
}
測(cè)試代碼：
int pAData[] = {10,34,68,98,20,8,7,6};
Node pA = new Node(0);
for(int i=pAData.length-1;i>=0;i--){
Node node = new Node(pAData[i]);
node.next = pA.next;
pA.next = node;
}
printLinkedList(pA);
int pBData[] = {21,5,8,7,6};
Node pB = new Node(0);
for (int i = pBData.length-1; i>=0;i--) {
Node node = new Node(pBData[i]);
node.next = pB.next;
pB.next = node;
}
printLinkedList(pB);
Node findNode = findFirstSameNode(pA, pB);
printLinkedList(findNode);
返回結(jié)果：
Linked List: 0->10->34->68->98->20->8->7->6->
Linked List: 0->21->5->8->7->6->
Linked List: 8->7->6->
