题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
首先将两个链表通过指针连接转变成两条相同长度（原先两条链表的长度之和）的链表，L1=P1+P2,L2=P2+P1,
其中L1表示P1链表加P2，L2同理可得。可以得知L1跟L2长度相同。
- 如果两个链表具有公共节点，那么从公共节点开始，L1、L2之后的节点都是相同的，而且后几个节点也是相同的。
- 如果两个链表不具有公共节点，说明已经遍历完L1、L2，此时只需判断是否完成遍历L1、L2即可。
因此只需要遍历一遍就可以判断是否具有公共节点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead2==null||pHead1==null)
return null;
ListNode p1=pHead1;
ListNode p2=pHead2;
while(p1!=p2){
p1=(p1!=null?p1.next:pHead2);
p2=(p2!=null?p2.next:pHead1);
if(p1==pHead1)
return null;
}
return p1;
}
}
查看15道真题和解析