刷题 : 相交链表

刷题 : 相交链表

题目链接: https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=problem-list-v2&envId=2cktkvj

题目说明

样例

解题思路

这个题就是尽可能遍历完两个链表

最好的方式还是每一个链表都交替一个元素, 这样保证能不错过最优解

用 map 存一下, 这个节点是否便利过

然后两个链表都遍历完, 肯定就可以得到结果了.

有点唐, 数组用多了, 不会写指针了 hhh

AC 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    map<ListNode*, bool> ma, mb;
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        for (ListNode *pa = headA, *pb = headB;;) {
            if (pa != NULL) {
                ma[pa] = 1;
                if (mb[pa])
                    return pa;
            }
            if (pb != NULL) {
                mb[pb] = 1;
                if (ma[pb])
                    return pb;
            }

            if (pa != NULL)
                pa = pa->next;
            if (pb != NULL)
                pb = pb->next;
            if (pa == NULL && pb == NULL) break ;
        }
        return NULL;
    }
};