输入两个链表，找出他们第一个公共节点

今天我来分享一下，输入两个链表，找出他们第一个公共节点的两种方式。

首先需要明确一点，如果两个链表有公共节点，那么从第一个公共节点开始，直到链表结束，这段链表的长度N对两个链表来说长度是一致的，且公共链表必定是从距离两个链表尾向前N（公共部分的节点个数）个节点的位置的下一位置开始的。

方式一（代码繁琐，易理解版）：

先给定两个指针使其能够表示两个链表的头结点（当前节点），首先让两个节点的长度保持一致，也就是确定好两个链表的长度length1,length2，使长度大的链表先遍历 |lenght1-lenght2| 个节点，让两个量表剩余节点个数一致后，然后依次对比两个链表的节点，直到找出公共节点或者链表走到尾部（未找到公共节点）为止。

图解：

代码如下：

#include<iostream>
using namespace std;
#include<stack>
#include<map>

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};

    int Size(ListNode* root){
        int i = 0;

        while(root != NULL){
            root = root->next;
            i++;
        }

        return i;
    }

    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* head1 = pHead1;
        ListNode* head2 = pHead2;
        int size1 = Size(head1);
        int size2 = Size(head2);
        head1 = pHead1;
        head2 = pHead2;

        if(size1 > size2){
            int pos = size1 - size2;
            while(pos > 0){
                head1 = head1->next;
                pos--;
            }
        }
        else{
            int pos = size2 - size1;
            while(pos > 0){
                head2 = head2->next;
                pos--;
            }
        }

        while(head1->val != head2->val){
            head1 = head1->next;
            head2 = head2->next;
        }

        return head1;
    }

int main()
{
	ListNode p1(5);
	ListNode p2(4);
	ListNode p3(3);
	ListNode p4(2);
	ListNode p5(1);

	p1.next = &p2;
	p2.next = &p3;
	p3.next = &p4;
	p4.next = &p5;
	p5.next = NULL;

	ListNode* tmp = FindFirstCommonNode(&p1, &p3);

	system("pause");
	return 0;
}

方法二（代码简易，理解略难版）

算法原理

假设链表一的长度为N，链表二的长度为M，Q为链表一和链表二长度差的绝对值。

N+M=M + N; <1>

if N>M，so N = M+Q;代入（1），N+M = N+(N-Q) = N-Q+N = M+N.;

else if N<M, so M = N+Q;代入（1），N+M = N+N+Q = N+Q+N = M+N;

else M=N, Q=0.显然可得。

图解

主要代码如下：

 ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;

        while(p1 != p2){
            if(p1 != NULL) p1 = p1->next; 
            if(p2 != NULL) p2 = p2->next;

if(p1 != p2){
     if(p1 == NULL) p1 = pHead2;
            if(p2 == NULL) p2 = pHead1;}
        }
        return p1;
    }

分享如上，望共同进步！