题解 | #两个链表的第一个公共结点#

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p=pHead1;
		ListNode* q=pHead2;
		while(p!=q){
			if(p){
				p=p->next;
			}else{
				p=pHead2;
			}
			if(q){
				q=q->next;
			}else{
				q=pHead1;
			}
		}
		return p;
    }
};

双指针实现，利用相同速度走过相等距离必相遇。

具体就是初始化两个指针分别指向两个链表，向后移动，一旦一方遇到空指针就继续从另一条链表的头结点开始遍历，若二者存在公共部分则会相遇即相等，否则都会同时遍历到末尾空指针，此时返回空指针。示例如下所示，都会遍历到6、7。

L1：1、2、6、7；L2：3、4、5、6、7；

1、2、6、7、3、4、5、6、7

3、4、5、6、7、1、2、6、7