leetcode160-相交链表

leetcode160

方法一:哈希表

思路:

• 先创建一个unordered_set,存放ListNode*类型的变量
• 先遍历其中一个链表,把所有节点的指针放在set中
• 再遍历另一个链表,查找是否存在一个节点已经在set中,如果存在则说明这是它们的相交节点的指针,返回这个指针,如果不存在则说明不存在相交节点,返回NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    unordered_set<ListNode*>hash;
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A=headA,*B=headB;
        while(A!=NULL){
            hash.insert(A);
            A=A->next;
        }   
        while(B!=NULL){
            if(hash.find(B)!=hash.end())
                return B;
            else
                B=B->next;
        }
        return NULL;
    }
};

方法二:双指针

思路:

• 让指针A和指针B分别指向headA和headB;A和B同时开始往后走,每次走一步,当A走到空时,就让A指向headB继续往后走;当B走到空时就让B指向headA继续往后走
• 最终一定会出现A=B,这时有两种情况:①A和B都指向空,这说明两个链表没有相交节点;②A和B指向同一个非空节点,这个节点就是相交节点
  最终会出现A=B的原因:假设两个链表长度分别为a和b,A是先走完a,再走完b,走的长度是a+b;B是先走完b,再走完a,走的长度是b+a,二者走的路程一样,最终肯定会指向同一个节点。

/**
 * 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*A=headA,*B=headB;
        while(true){
            if(A==NULL && A!=B)
                A=headB;
            if(B==NULL && B!=A)
                B=headA; 
            if(A==B)
                return A;
            if(A==NULL && B==NULL)
                return NULL;
            A=A->next;
            B=B->next;
        }
        return NULL;
    }
};