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

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）。

思路

两个单链表有公共的节点，说明这两个链表从某一个节点开始，他们的next都指向同一个节点。两个链表从不同的地方开始，结束的地方相同。通过遍历两个链表了解两个链表的长度，先遍历长度较长的链表，等到较长链表剩余部分与较短的链表长度相同时开始比较两个链表的数据。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        int head1_num=0, head2_num=0;
        ListNode* p1=pHead1;
        ListNode* p2 = pHead2;
        //遍历两个链表，获得两个链表的长度。
        while (p1 !=NULL)
        {
            head1_num++;
            p1 = p1->next;
        }
        while (p2 !=NULL)
        {
            head2_num++;
            p2 = p2->next;
        }
        ListNode* result=NULL;
        //先遍历长度较长的链表
        if (head1_num >=head2_num) {
            for (int i = 0; i <head1_num- head2_num; i++)
            {
                pHead1 = pHead1->next;
            }
        }
        else
        {
            for (int i = 0; i <head2_num-head1_num; i++)
            {
                pHead2 = pHead2->next;
            }
        }
        //剩余两个链表长度相同，开始比较链表中的数据
        while (pHead1!=NULL)
        {
            if (pHead1->val == pHead2->val) {
                result = pHead1;
                return result;
            }
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return result;

    }
};