题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/
下面两种方法都想到了,官方题解的双指针法想不到。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/** * 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* hb = headB; while (headA) { headB = hb; while (headB) { if (headB == headA) { return headA; } headB = headB->next; } headA = headA->next; } return NULL; } */ ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> s; while (headA) { s.insert(headA); headA = headA->next; } while (headB) { if (s.count(headB) > 0) { return headB; } headB = headB->next; } return NULL; } }; |