剑指36-两个链表中第一个共同的节点

链表

首先这个题目关键的地方就是，这个共同节点到底是什么。

假如有两个链表如下：

解法

两个链表中，值为6的节点为同一节点，这就是共同节点，
但是两个链表长度不同，不能都从头遍历，
所以先找到长度差，长的链表先走，直到两个链表长度相同，再同时遍历两个链表

#include <iostream>

using namespace std;

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


class Solution {
public:
    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        int len1 = 0, len2 = 0, diff = 0;
        while (p1 != NULL) {  //计算pHead1的长度
            p1 = p1->next;
            len1++;
        }
        while (p2 != NULL) { //计算pHead2的长度
            p2 = p2->next;
            len2++;
        }
        if (len1 > len2) {  //p1放最长的链表
            diff = len1 - len2;
            p1 = pHead1;
            p2 = pHead2;
        }
        else {
            diff = len2 - len1;
            p1 = pHead2;
            p2 = pHead1;
        }
        for (int i = 0; i < diff; i++) {  //这里的原理是，公共节点肯定在p1和p2共同长度的节点上，所以p1先走多出的diif长度，在一起判断
            p1 = p1->next;
        }
        while (p1 != NULL && p2 != NULL) {
            if (p1 == p2) {
                cout << p1 ->val;
                break;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};

void main()
{
    ListNode* pHead1 = new ListNode(1);
    ListNode* pt1=pHead1;
    pt1->next = new ListNode(2);
    pt1 = pt1->next;
    pt1->next = new ListNode(3);
    pt1 = pt1->next;
    ListNode* root = new ListNode(2);
    pt1->next = root;
    pt1 = pt1->next;
    pt1->next = new ListNode(1);
    pt1 = pt1->next;


    ListNode* pHead2 = new ListNode(4);
    ListNode* pt2 = pHead2;
    pt2->next = new ListNode(5);
    pt2 = pt2->next;
    pt2->next = root;
    pt2 = pt2->next;
    pt2->next = new ListNode(1);
    pt2 = pt2->next;

    Solution s;
    s.FindFirstCommonNode(pHead1, pHead2);
}