題意

給定兩個鏈表，找這兩個鏈表第一個公共節點，如果沒有返回nullptr

題目鏈接

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

題解

兩個指針分別從兩個鏈表（記錄為表A，表B）的表頭出發，并且記錄到表尾移動的步數，得到兩個指針移動的步數之差$x$。步數之差為正數，那么把表A的指針移動$x$步，否則移動表B的指針$?x$步。然后兩個指針移動到表尾，得到答案。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1 = headA;ListNode *p2 = headB;int cnt1 = 0;int cnt2 = 0;while(p1) {p1 = p1->next;cnt1++;}while(p2) {p2 = p2->next;cnt2++;}p1 = headA;p2 = headB;int cnt3 = abs(cnt1 - cnt2);if(cnt1 >= cnt2) {for(int i = 0; i < cnt3; i++) {p1 = p1->next;}} else {for(int i = 0; i < cnt3; i++) {p2 = p2->next;}            }while(p1 != p2 && p1 != nullptr) {p1 = p1->next;p2 = p2->next;}return p1 == nullptr ? nullptr : p1;}
};

算法復雜度:$O(m+n)$， $m$，$n$分別為兩個表的長度
空間復雜度:$O(1)$