【剑指offer】面试题52：两个链表的第一个公共节点——栈、哈希表、双指针

方法一：哈希表

/** * 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) {
    
        unordered_map< ListNode*, int > record;
        if( headA == nullptr || headB == nullptr)
            return nullptr;
        while( headA != nullptr )
        {
    
                record[headA]++;
                headA = headA->next;
        }
        while( headB != nullptr )
        {
    
            
            if( ( ++record[headB] ) >= 2)
                return headB;
            headB = headB->next;
        }
        return 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) {
    
        ListNode *L1=headA;
        ListNode *L2=headB;
        if( headB == nullptr || headA == nullptr)
            return NULL;

        while( L1 != L2 )
        {
    
            L1 = L1 != NULL ? L1->next : headB;
            L2 = L2 != NULL ? L2->next : headA;
        }
        return L1;

    }
};

方法三：栈实现

将所有的节点地址的数据推入到栈中，再后进先出
比较后面相同的数据，如果遇到了不同的数据则把上一次相同的最后一个节点返回就好了。

/** * 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 == nullptr || headA == nullptr)
            return NULL;
        stack< ListNode* > stack_L1;
        stack< ListNode* > stack_L2;
        ListNode* tempL1 = nullptr;
        ListNode* tempL2 = nullptr;

        

        
        while( headA != nullptr )
        {
    
            stack_L1.push(headA);
            headA = headA->next;    
        }
        while( headB != nullptr )
        {
    
            stack_L2.push(headB);
            headB = headB->next;
        }
        ListNode* result = nullptr;
        while( !stack_L1.empty() && !stack_L2.empty() )
        {
    
        
            if( !stack_L1.empty() )
                tempL1 = stack_L1.top();
            if( !stack_L2.empty() )
                tempL2 = stack_L2.top();
            

            if( tempL1 != tempL2 )
                break;
            
            result = stack_L1.top();
            if( !stack_L1.empty() ) stack_L1.pop();
            if( !stack_L2.empty() ) stack_L2.pop();
        }
        return result;

    }
};