Leetcode 160. Intersection of Two Linked Lists

Tyan

发布于 2019-05-25 23:26:14

2150

发布于 2019-05-25 23:26:14

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan

博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

Version 1

/**
 * 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*, ListNode*> m;
        ListNode* current = headA;
        while(current) {
            m[current] = current;
            current = current->next;
        }
        current = headB;
        while(current) {
            if(m.find(current) != m.end()) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }
};

Version 2

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