題目描述

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回 null 。
圖示兩個鏈表在節點 c1 開始相交：

題目數據 保證 整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須 保持其原始結構 。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *p1=headA;ListNode *p2=headB;while (p1!=p2){if(p1!= nullptr){p1=p1->next;} else{p1=headB;}if(p2!= nullptr){p2=p2->next;} else{p2=headA;}}return p1;}
};

小結：鏈表題好久沒做了，從這里重新回憶起來鏈表的內容，這道題思路很巧妙，如圖（來自力扣題解）第一個指針p1走a+b-c，第二個指針走b+a-c，如果有公共結點，那么按照這種遍歷方法一定會重合