大家好呀，我是直男蛋。
今天来做相交链表，这道题本来是难度简单的水题，但是有两个奇怪点把我给整楞了。
一个就是题意，另一个就是解题方式，感觉直接把我的直男属性给暴露了。
具体的到下面细聊，现在先开始看题。
LeetCode 160：相交链表
题意
给出两个单链表的头节点，找出两个单链表相交的起始节点。
示例
提示
题目保证不存在环。
len(listA) = m, len(listB) = n
0 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m, 0 <= skipB <= n
题目解析
在说我的解法之前，我先来说一下文章开头我说的是啥意思。
这个题目一开始题意给我看楞了，不看示例，打眼看上去还以为是找数值相等的节点。
估计很多臭宝容易看懵，这道题其实是找相交节点的指针（即同一节点，引用完全相同），而不是单纯遍历找第一个数值相同的节点，这点大家要搞清楚。
光这个出题的题意，我感觉就得值个难度 hard！
其实搞清楚了题意，稍微一想解法就能出来。
在我劈里啪啦的敲完代码然后 AC 的时候，随意点开了力扣的题解区，官方的题解给我看楞了。
虽然用了双指针，但是它的解法楞是用上了数学的思想。
怕你们在做的时候会先去看题解，然后又看不懂别人怎么个思想，所以这里就给臭宝们讲一下“浪漫”的做法。
官方的方法是：
- 链表 A 的指针 flagA 从链表 A 的头节点开始遍历完链表 A，再遍历链表 B
- 链表 B 的指针 flagB 从链表 B 的头节点开始遍历完链表 B，再遍历链表 A
这样的话就消除了链表 A 和 B 的长度差。
假设链表 A 长度为 a，链表 B 长度为 b，两个链表相交的部分长度为 c。
当走到相交节点时：
- flagA 走过的长度为：a + (b - c)
- flagB 走过的长度为：b + (a - c)
这种做法，不管两个指针是否相交，他们走过的长度都是一样的，所以就有了公式：
a + (b - c) = b + (a - c)
若两个链表能相交，那么 c > 0，两个指针同时指向相交节点。
若两个链表不相交，那么 c = 0，两个指针同时指向 Null。
是不是很巧妙的做法，时间复杂度 O(n+m)，空间复杂度为 O(1)。
看了一下评论，浪漫气息弥漫：
看到这我应该非常肯定自己是个废物了。
本应该拍手称快，但是这解法属实让我愣了：这还是一道简单题？
我感觉我等凡人，不在草稿纸上划拉划拉，一下子也看不懂它的题解是什么意思，更不用说在面试或者比赛中想出这样的解法了。
好了，这个解法就说到这吧。
下面，该是本直男蛋的做法了，比起人家的解法我这简直是俗不可耐，但保证看一眼就能看明白。
我也用到了双指针，不过我是从屁股开始的。
你想，如果两个链表相交的话，那必定有一段公共段。
既然有这个前提，那公共段以前的对比那是白送的无用功。
让长链表先走“两个链表长度的差值”，然后链表从长度相同的位置开始同步向后遍历。
找到相交节点，则返回节点，如果没相交节点的话，两个指针都指向 Null。
光这么说可能不好理解，下面来看图解。
图解
我以 listA = [0, 9, 1, 2, 4]、listB = [3, 2, 4] 为例，相交节点的值为 2。
指向 listA 和 listB 的指针分别为 flagA 和 flagB，两个链表的长度分别用 lenA 和 lenB 表示。
首先初始化两个指针和链表长度。
# 初始化headA、headB的指针和长度 flagA, flagB = headA, headB lenA, lenB = 0, 0
然后计算两个链表长度的差值
# 求链表 A 的长度 while flagA: flagA = flagA.next lenA += 1 # 求链表 B 的长度 while flagB: flagB = flagB.next lenB += 1
在本例中，链表 A 比链表 B 长，差值为 2，所以链表 B 的指针 flagB 移动差值的距离。
# 当A是长链表，则指针flagA后移到和B链表同等长度的位置上。 if lenA > lenB: d_value = lenA - lenB while d_value: flagA = flagA.next d_value -= 1
之后 flagA 和 flagB 同时向后遍历。
flagA = flagA.next flagB = flagB.next
如果找到 flagA 和 flagB 指向相同，即相遇，则返回指针，否则继续遍历，直到两个指针都指向 Null，表明没有交点。
本例中相遇节点为 2。
if flagA == flagB: return flagA
我这个解法比起人家那个浪漫的确实 low 了点，但是复杂度上完全不输。
链表 headA 和 headB 各遍历了一遍，时间复杂度同样为 O(n + m)。
同时也没整额外的存储，空间复杂度为 O(1)。
我要骄傲了呀。
代码实现
Python 代码实现
为了让大家看明白点，代码我用了最简单粗暴的形式写的，一点炫技都没加，保证能看懂。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: # 链表A和B任一为空，链表不相交 if not headA or not headB: return None # 初始化headA、headB的指针和长度 flagA, flagB = headA, headB lenA, lenB = 0, 0 # 求链表 A 的长度 while flagA: flagA = flagA.next lenA += 1 # 求链表 B 的长度 while flagB: flagB = flagB.next lenB += 1 # 重新指向表头 flagA, flagB = headA, headB # 为了让大家看的明白点，我就不用华丽花哨的写法了，用最笨的写法表示。 # 当A是长链表，则指针flagA后移到和B链表同等长度的位置上。 if lenA > lenB: d_value = lenA - lenB while d_value: flagA = flagA.next d_value -= 1 # 当B是长链表，则指针flagB后移到和A链表同等长度的位置上。 else: d_value = lenB - lenA while d_value: flagB = flagB.next d_value -= 1 # 然后两个指针flagA和flagB同时遍历 while flagA: if flagA == flagB: return flagA else: flagA = flagA.next flagB = flagB.next # 如果没有相遇，返回 None return None
Java 代码实现
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; int lenA = 0, lenB = 0; while (curA != null) { // 求链表A的长度 lenA++; curA = curA.next; } while (curB != null) { // 求链表B的长度 lenB++; curB = curB.next; } curA = headA; curB = headB; // 让curA为最长链表的头，lenA为其长度 if (lenB > lenA) { //1. swap (lenA, lenB); int tmpLen = lenA; lenA = lenB; lenB = tmpLen; //2. swap (curA, curB); ListNode tmpNode = curA; curA = curB; curB = tmpNode; } // 求长度差 int gap = lenA - lenB; // 让curA和curB在同一起点上（末尾位置对齐） while (gap-- > 0) { curA = curA.next; } // 遍历curA 和 curB，遇到相同则直接返回 while (curA != null) { if (curA == curB) { return curA; } curA = curA.next; curB = curB.next; } return null; } }
图解相交链表到这就结束了，可算写完了，差点写的累死。
没想到没被题困住，差点被题意堵死。
道理明白了就好啦，重要的是解题思路，而不是题本身，这次讲的这两个思路都蛮有意思的，大家细细揣摩。
揣摩之前先点赞在看，养成好习惯，有问题留言区见。
我是蛋蛋，我们下次见！
