题目描述

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

当不存在公共节点时，返回空节点。

样例

给出两个链表如下所示：
A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

算法

(链表)

1. 一开始计算len1和len2直接用的cur和curB，这样不对，因为len1和len2计算完后，cur和curB对应的节点也变化了。

时间复杂度

$O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        int len1 = 0, len2 = 0;
        auto cur = headA;
        auto curB = headB;

        /*
        for(; cur; cur = cur->next) len1 ++;
        for(; curB; curB = curB->next) len2 ++;
        */

        for(auto t = headA; t; t = t->next) len1 ++;
        for(auto t = headB; t; t = t->next) len2 ++;


        int step = len1 > len2 ? len1 - len2 : len2 - len1;

        if(len1 > len2)
            while(step --) cur = cur->next;
        else
            while(step --) curB = curB->next;

        while(cur && curB)
        {
            if(cur == curB) return cur;
            cur = cur->next;
            curB = curB->next;
        }

        return nullptr;
    }
};

看别人的题解好像还有一种方法，先mark上，后面补上！