剑指 Offer II 023. 两个链表的第一个重合节点

剑指 Offer II 023. 两个链表的第一个重合节点

题目描述

给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

双指针

双指针的想法其实很巧妙，两个指针分别指向headA 和 headB的头结点，但是当二者走到链表的尾结点的时候，指针指向互换。

那么如果有重合的结点，那么两个指针肯定在重合结点相遇。

如果没有重合结点，两个指针都指向 nullptr，结束循环。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        ListNode* ptr1 = headA;
        ListNode* ptr2 = headB;

        while(ptr1 != ptr2){
            ptr1 = ptr1 == nullptr? headB : ptr1->next;
            ptr2 = ptr2 == nullptr? headA : ptr2->next;
        }
        return ptr1;
    }
};

哈希表

哈希表思路就比较好理解了 ，直接先遍历一个链表，哈希表中插入全部结点。

接着遍历另一个链表，如果哈希表中存在这个结点，那么就是重合结点，直接返回。

否则没有重合结点，直接返回nullptr

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
         unordered_set<ListNode*> hashs;

        while(headA != nullptr){
            hashs.insert(headA);
            headA = headA->next;
        }

        while(headB != nullptr){
            if(hashs.count(headB)) return headB;
            headB = headB->next;
        }
        return nullptr;
    }
};