大学虽然在打 ACM ，但为了之后夏令营准备机试或者之后面试的机试的时候准备写一下 leetcode 上的 hot100 时感觉题目风格或者知识点上还是有比较大的差异（板子抄多了以及基础数据结构不太写导致的（）），所以打算从头做一遍顺便基本整理一下
- 应该使用 nullptr 而不是 null，nullptr 是 C++11 引入的空指针常量，表示"不指向任何地址的指针"
- 如果是对象的话可以直接用
.，含义是访问成员（变量，函数等）；但如果是指针的话只能使用->，因为要先解引用再访问成员
不难想到用一个数组去存一下一个链表中一个节点有没有出现过，在遍历另一条链的时候进行判断
但因为是要尾部全部相同，所以要逐个判断是否相同，不相同的话就要更新
/*** 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) {vector<int> vis(10005);auto cur = headA;while (cur != nullptr) {vis[cur->val] = 1;cur = cur->next;}cur = headB;ListNode *ans = nullptr;while (cur != nullptr) {if (vis[cur->val]) {if (ans == nullptr) {ans = cur;}} else {ans = nullptr;}cur = cur->next;}return ans;}
};
这样是值相同，不是内存地址相同
所以物理地址的话要直接存储指针
/*** 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_set<ListNode *> st;while (headA != nullptr) {st.insert(headA);headA = headA->next;}while (headB != nullptr) {if (st.find(headB) != st.end()) {return headB;}headB = headB->next;}return headB;}
};
进阶
要求时间复杂度 O(n + m)，空间复杂度 O(1)
也就是没有额外的空间让我们存储信息了
时间复杂度指引我们继续考虑连续遍历两条链
既然没法维护信息，那么考虑在遍历的过程中能做些什么
上面是一次遍历，也就是从 A 开始的，那么要做些变化的话，想到同时遍历，也就是一个从 A 出发，一个从 B 出发
发现因为尾部是相同的，而 两条链 并起来走的时候长度又是相同的
也就是它们会直接走到那一个交点上
但是注意不能这样写
/*** 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) {while (headA != headB) {headA = headA != nullptr ? headA->next : headB;headB = headB != nullptr ? headB->next : headA;}return headA;}
};
因为这样相当于 headA 和 headB 在发生变化，这样走完一条要走另一条的时候找不到头节点
/*** 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) {auto a = headA, b = headB;while (a != b) {a = a != nullptr ? a->next : headB;b = b != nullptr ? b->next : headA;}return a;}
};