36.两个链表的第一个公共结点.md

36.两个链表的第一个公共结点

题目描述

• 输入两个链表，找出它们的第一个公共结点。

 

解题思路

下面的思路来自《剑指offer》。

如果两个链表有公共结点，那么从这个公共结点开始，以下的全都是一样的。

• 思路一，利用两个栈，从两个链表的底部开始对比。先将两个链表的所有结点依次入栈，然后从链尾开始对比，直到两个结点地址不相等。
• 思路二，砍头同步遍历法。先对两个链表分别进行遍历，得到两个链表的长度，把长的那个链表头部多的几个结点砍掉（从长的链表上先走几步），这样两个链表就等长了，然后两个链表一起向后遍历，当两个结点地址一样的时候就找到了。

 

代码

• 思路二，砍头同步遍历法

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==NULL || pHead2==NULL) return NULL;
        ListNode *p1=pHead1, *p2=pHead2;
        // 统计长度
        int len1=0, len2=0;
        while(p1){
            len1++;
            p1 = p1->next;
        }
        while(p2){
            len2++;
            p2 = p2->next;
        }
        // 对齐
        p1 = pHead1;
        p2 = pHead2;
        while(len1>len2){
            p1 = p1->next;
            len1--;
        }
        while(len2>len1){
            p2 = p2->next;
            len2--;
        }
        // 寻找公共结点
        while(p1 != p2){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};