day1 相交链表

上一次用 cpp 还是上一次，连指针用法都不记得了。

读题

有两头结点 headA 与 headB，若两个单链表交于某节点，找出并返回；若没有相交，返回 null。
不能破坏链表原始结构，链表中无环。
有链表节点结构：

struct ListNode {
    int val;
    ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

• listA 中有 m 个节点，listB 中有 n 个
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶： 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

过程

第一思路

遍历，两个循环嵌套，判断 A 的某个节点的下个节点是否是 B 中当前节点的下一个节点，即 ListNode *next 相同。时间复杂度是 O(m*n)。
于是按照以上想法写了代码：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
	for(int i=0; i<30000; i++){
		for(int j=0; j<30000; j++){
			if((*(headA+i)).next == NULL || (*(headB+j)).next == NULL) return NULL;
			if (&(*(headA+i)).next == &(*(headB+j)).next)
				return (*(headA+i)).next;
		}
	}
	return NULL;
}

很唐的错误

• if((*(headA+i)).next == NULL || (*(headB+i)).next == NULL) return NULL;
  • 第一遍这么写了，回头一看简直唐完了
  • headA+i 不是人类能写出来的东西
• For 循环嵌套
  • 完全没有必要

第二思路

首先，我有 ListNode *headA 和 ListNode *headB，是两个单链表的头节点。我应该使用单独两个指针 ListNode *listNodeA 和 ListNode *listNodeB（而不是 *(headA+i) 这种东西）来遍历链表 A 和 B，使用 while 循环即可。
其次，判断相交（有共同节点）应该是指针指向的地址相同，也就是指针相同（大概）。
最后，判断遍历结束应该是两边都结束了。
于是有代码：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
	ListNode* listNodeA = headA;
	ListNode* listNodeB = headB;
	while (listNodeA != NULL){
		while(listNodeB != NULL){
			if(listNodeA == listNodeB)
				return listNodeA;
			listNodeB = listNodeB->next;
		}
		listNodeA = listNodeA->next;
	}
	return NULL;
}

这次通过了一个测试，另外两个没过，打开一看，输出全是“没有相交”；仔细一看是少了 B 指针的重新初始化。改成了：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
	ListNode* listNodeA = headA;
	ListNode* listNodeB = headB;
	while (listNodeA != NULL){
		listNodeB = headB;
		while(listNodeB != NULL){
			if(listNodeA == listNodeB)
				return listNodeA;
			listNodeB = listNodeB->next;
		}
		listNodeA = listNodeA->next;
	}
	return NULL;
}

提交之后正确了。

结果

执行用时 662 ms，消耗内存 18 MB，堪称巨大一坨， O(n^2) 导致的。
看了官方题解，有哈希集合和所谓双指针法，都是 O(m+n) 也就是 O(n)。
另外，需要注意两个链表均为空的情况，我没有注意到。

哈希集合

遍历 A，将节点加入哈希集合；遍历 B，判断每个节点是否在哈希集合中。

双指针法

A 和 B 指针同时移动。假设 m 小于 n，那么 A 链表会先遍历结束，这时将指针 A 移动到链表 B 的头节点，于是 A 和 B 指针之间间隔了 m 个节点。继续移动。
在以上过程中，如果 A 和 B 指针指向同一个节点，那么返回那个节点；如果都为空，返回 null。
如果：

• 遍历结束 A 之前指向同一个节点
• 遍历结束 A 之后，又遍历了 B，假设 c 是 AB 共同部分长度，这时 A 和 B 之间间隔了 m+n-c 个节点。可以证明二者能同时达到相交的节点。
• 遍历结束 A 之后，又遍历了 B，但是没有找到相交节点而是都为空了，说明不存在相交节点。
  这太酷了，完全符合我对“算法”二字的想象。

抽象方法

评论区大佬言：
作弊算法：A走一遍把值取负，B走一遍发现第一个负数就是相交点，最后再把A的值改回来
相当于给链表 A 的节点做上标记，B 按顺序搜索时碰到打了标记的，就说明相交了，所谓”原地哈希”，但是本题不能修改原链表的值所以不太能这么操作。

修改

按照双指针法，修改了代码：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
	if (!headA || !headB)
		return NULL;
	ListNode* listNodeA = headA;
	ListNode* listNodeB = headB;
	while (listNodeA != listNodeB) {
		if(listNodeA)
		    listNodeA = listNodeA->next;
		else listNodeA = headB;
		if(listNodeB)
		    listNodeB = listNodeB->next;
		else listNodeB = headA;
	}
	return listNodeA;
}

大致就是在 AB 指针不相同的情况下一直往下走，直到 AB 指针指向同一个。不过写法是不如三目运算优雅的。
于是 39 ms 用时，不过内存仍然是吃了 18 MB。

收获

回忆了指针的用法，学习到了哈希集合和双指针法；但是没有吃透，下次遇到不一定用得出来。