当前位置：首页 > article >正文

leetcode之hot100---160相交链表（C++）

article 2024/12/22 11:18:35

思路一：哈希表法

把其中一个链表中的值存入哈希表中，然后在这个构建的哈希表中寻找另一链表中的值

/**
 * 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 == NULL || headB == NULL) {
            return NULL;
        }
        //创建一个哈希表用于存储链表headA中的值
        unordered_set<ListNode*> copy_headA;
        //声明一个指针
        ListNode *p = headA;
        //将headA中的值存入哈希表中
        while(p != NULL){
            copy_headA.insert(p);
            p = p->next;
        }
        //在哈希表中寻找headB的值，找到第一个就说明后续全部重合
        p = headB;
        while(p != NULL){
            auto it = copy_headA.find(p);
            if(it != copy_headA.end()){
                return p;
            }
            p = p->next;
        }
        return NULL;
    }
};

看官方题解空值使用的是nullptr，这是相较于NULL更安全的一种空值表示

时间复杂度：O(headA.length+headB.length)
空间复杂度：O(headA.length)

思路二：双指针法

使用两个指针分别指向两个链表的头部，环状检查是否有重合部分

/**
 * 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 == NULL || headB == NULL){
            return NULL;
        }
        ListNode *p = headA;
        ListNode *q = headB;
        while(p != q){
            p = p == NULL ? headB : p->next;
            q = q == NULL ? headA : q->next;
        }
        return p;
    }
};

当指向headA的指针遍历完headA中的所有节点后指向headB的原因是：

指向headA和headB的指针是同时移动的，如果重合部分之前的移动次数不一样，会导致判断失败，举个例子说明：

A: 1->2->3->8->9

B: 5->6->8->9

其中8是交点：

pA走：1->2->3->8->9->5->6->8
pB走：5->6->8->9->1->2->3->8