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

116 阅读 0 评论 77 点赞

我是靠谱客的博主舒适黄蜂，最近开发中收集的这篇文章主要介绍输入两个链表，找出他们第一个公共节点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

 
 首先需要明确一点，如果两个链表有公共节点，那么从第一个公共节点开始，直到链表结束，这段链表的长度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;
    }