鏈表相交

力扣題目鏈接

暴力解法:飄過

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * cur = headA;while(cur != NULL){ListNode* curb = headB;while(curb != NULL){if(curb==cur){return cur;}curb = curb->next;}cur = cur->next;}return NULL;}
};

非暴力解法：

看如下兩個鏈表，目前curA指向鏈表A的頭結點，curB指向鏈表B的頭結點：

我們求出兩個鏈表的長度，并求出兩個鏈表長度的差值，然后讓curA移動到，和curB 末尾對齊的位置，如圖：

此時我們就可以比較curA和curB是否相同，如果不相同，同時向后移動curA和curB，如果遇到curA == curB，則找到交點。

否則循環退出返回空指針。

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * cur = headA;ListNode* curb = headB;int counta=0;int countb=0;while(cur != NULL){counta++;cur = cur->next;}while(curb != NULL){countb++;curb = curb->next;}cur = headA;curb = headB;int n = 0;if(counta > countb){n = counta - countb;for(int i =0 ;i<n;i++){cur = cur->next;}}else{n = countb - counta;for(int i =0 ;i<n;i++){curb = curb->next;}}while(cur != NULL && curb !=NULL){if(cur == curb){return cur;}cur = cur->next;curb = curb->next;}return NULL;}
};