声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
题目:给定两个单向链表,计算两个链表的第一个公共结点,若没有公共节点,返回空
令两链表的长度为m,n,不妨认为m>=n,由于两个链表从第一个公共结点到链表的尾结点是完全重合的.所以前面的(m-n)个结点一定没有公共结点
算法:先分别遍历两个链表得到它们的长度m,n.长链表空转(m-n)次,同步遍历两链表,直至找到相同结点或到链表结束
时间复杂度O(m+n)
Java版本实现:
public static Node findFirstSameNode(Node pA, Node pB){
//因为有头指针,所以指向第一个有效结点
pA = pA.next;
pB = pB.next;
//计算两个链表的长度
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;
}
//空转nB-nA次
for(int i=0;i<nB-nA;i++){
pB = pB.next;
}
//齐头并进
while(pA != null){
if (pA.value == pB.value) {
return pA;
}
pA = pA.next;
pB = pB.next;
}
return null;
}
测试代码：
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);
返回结果：
Linked List: 0->10->34->68->98->20->8->7->6->
Linked List: 0->21->5->8->7->6->
Linked List: 8->7->6->
