题解 | #两个链表的第一个公共结点#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* l1 = pHead1;
        ListNode* l2 = pHead2;
        while (l1 != l2) {
            l1 = (l1 == nullptr) ? (pHead2) : (l1->next);
            l2 = (l2 == nullptr) ? (pHead1) : (l2->next);
        }
        return l1;
    }
};

时间复杂度：O(N+M) 空间复杂度O(1)

解题思路：两个链表，有公共交点，交点所处的链表各自的位置不同。

1.思想是把两个链表串联在一起

2.串联成两份，用两个指针各自同时遍历自己的一份

3.当节点相同时，即为交叉点

4.while循环，当两个节点相同时结束，若没有交叉点，则会则各自的节点末尾退出while循环