leetcode160. 相交链表

哈希

/**
 * 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 *temp=headA;
       unordered_set<ListNode*>set;
       while(temp){
           set.insert(temp);
           temp=temp->next;
       }
       temp=headB;
       while(temp){
           if(set.count(temp))
            return temp;
            temp=temp->next;
       }
        return nullptr;
    }
};

双指针

a+b的节点数是一样的，从a,b开始走，a走到头后回到b走，同理，b走到头后回到a走，两者如果有公共节点一定会相遇，否则a,b都会走到nullptr退出。

/**
 * 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) {
       if(!headB||!headA)return nullptr;
       ListNode* pa=headA,*pb=headB;
       while(pa!=pb){
           pa=pa==nullptr?headB:pa->next;
           pb=pb==nullptr?headA:pb->next;
       }
        return pa;
    }
};