描述：
输入两个链表，找出它们的第一个公共结点；
注：链表为单链表
-
法一：
分析：
使用双重循环，依次遍历pHead1,pHead2的所有结点，若相同则返回即可。
实现：
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1==null||pHead2==null)
return null;
ListNode cur1=pHead1;
ListNode cur2=pHead2;
while (cur1!=null){
if (cur1.val==cur2.val)
return cur1;
else {
while (cur2!=null){
if (cur1.val==cur2.val)
return cur1;
else {
cur2=cur2.next;
}
}
cur2=pHead2;
cur1=cur1.next;
}
}
return null;
}
-
法二：
分析：
由于是单链表，当出现公共结点后，其后部分均为相同。（因为2个链表用公共的尾部）
当两个链表存在公共结点的时候：
- 当链表长度相同的时候，由于有着公共的尾部，直接同时开始遍历，一定会找到第一个共同结点；
- 当链表长度不同的时候，让长链表先开始多出的那部分，当长链表的剩余长度与短链表的长度相同的时候，两个链表同步开始，这时就转化为了链表长度相同的时候。
那么，在该题中
- 计算两个链表的长度（size1,size2）
- 根据长度判断，让长链表先开始|size1-size2|
- 两个链表同步遍历，当出现的第一个相同的元素就是公共结点的第一个。
实现：
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int size1 = findNodeSize(pHead1);
int size2 = findNodeSize(pHead2);
if (size1>size2){
pHead1 = walkStepNode(pHead1, size1 - size2);
}else {
pHead2= walkStepNode(pHead2, size2 - size1);
}
while (pHead1!=null){
if (pHead1==pHead2)
return pHead1;
pHead1=pHead1.next;
pHead2=pHead2.next;
}
return null;
}
private int findNodeSize(ListNode p){
int count=0;
while (p!=null){
count++;
p=p.next;
}
return count;
}
private ListNode walkStepNode(ListNode p,int step){
while (step-->0){
p=p.next;
}
return p;
}
