LeetCode 160：相交鏈表
往期鏈表文章：
圖解 LeetCode 141：鏈表，你有環(huán)嘛？
今天來做相交鏈表，這道題本來是難度簡單的水題，但是有兩個奇怪點(diǎn)把我給整楞了。
一個就是題意，另一個就是解題方式，感覺直接把我的直男屬性給暴露了。
具體的到下面細(xì)聊，現(xiàn)在先開始看題。
LeetCode 160：相交鏈表
題意
給出兩個單鏈表的頭節(jié)點(diǎn)，找出兩個單鏈表相交的起始節(jié)點(diǎn)。
示例
提示
題目保證不存在環(huán)。
len(listA) = m, len(listB) = n
0 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m, 0 <= skipB <= n
題目解析
在說我的解法之前，我先來說一下文章開頭我說的是啥意思。
這個題目一開始題意給我看楞了，不看示例，打眼看上去還以為是找數(shù)值相等的節(jié)點(diǎn)。
估計(jì)很多臭寶容易看懵，這道題其實(shí)是找相交節(jié)點(diǎn)的指針（即同一節(jié)點(diǎn)，引用完全相同），而不是單純遍歷找第一個數(shù)值相同的節(jié)點(diǎn)，這點(diǎn)大家要搞清楚。
光這個出題的題意，我感覺就得值個難度 hard！
其實(shí)搞清楚了題意，稍微一想解法就能出來。
在我劈里啪啦的敲完代碼然后 AC 的時(shí)候，隨意點(diǎn)開了力扣的題解區(qū)，官方的題解給我看楞了。
雖然用了雙指針，但是它的解法楞是用上了數(shù)學(xué)的思想。
怕你們在做的時(shí)候會先去看題解，然后又看不懂別人怎么個思想，所以這里就給臭寶們講一下“浪漫”的做法。
官方的方法是：
鏈表 A 的指針 flagA 從鏈表 A 的頭節(jié)點(diǎn)開始遍歷完鏈表 A，再遍歷鏈表 B
鏈表 B 的指針 flagB 從鏈表 B 的頭節(jié)點(diǎn)開始遍歷完鏈表 B，再遍歷鏈表 A
這樣的話就消除了鏈表 A 和 B 的長度差。
假設(shè)鏈表 A 長度為 a，鏈表 B 長度為 b，兩個鏈表相交的部分長度為 c。
當(dāng)走到相交節(jié)點(diǎn)時(shí)：
flagA 走過的長度為：a + (b - c)
flagB 走過的長度為：b + (a - c)
這種做法，不管兩個指針是否相交，他們走過的長度都是一樣的，所以就有了公式：
a + (b - c) = b + (a - c)
若兩個鏈表能相交，那么 c > 0，兩個指針同時(shí)指向相交節(jié)點(diǎn)。
若兩個鏈表不相交，那么 c = 0，兩個指針同時(shí)指向 Null。
是不是很巧妙的做法，時(shí)間復(fù)雜度 O(n+m)，空間復(fù)雜度為 O(1)。
看了一下評論，浪漫氣息彌漫：
錯的人就算走過了對方的路也還是會錯過。
走到盡頭見不到你，于是走過你來時(shí)的路，等到相遇時(shí)才發(fā)現(xiàn)，你也走過我來時(shí)的路。
看到這我應(yīng)該非?？隙ㄗ约菏莻€廢物了。
本應(yīng)該拍手稱快，但是這解法屬實(shí)讓我愣了：這還是一道簡單題？
我感覺我等凡人，不在草稿紙上劃拉劃拉，一下子也看不懂它的題解是什么意思，更不用說在面試或者比賽中想出這樣的解法了。
好了，這個解法就說到這吧。
下面，該是本直男蛋的做法了，比起人家的解法我這簡直是俗不可耐，但保證看一眼就能看明白。
我也用到了雙指針，不過我是從屁股開始的。
你想，如果兩個鏈表相交的話，那必定有一段公共段。
既然有這個前提，那公共段以前的對比那是白送的無用功。
讓長鏈表先走“兩個鏈表長度的差值”，然后鏈表從長度相同的位置開始同步向后遍歷。
找到相交節(jié)點(diǎn)，則返回節(jié)點(diǎn)，如果沒相交節(jié)點(diǎn)的話，兩個指針都指向 Null。
光這么說可能不好理解，下面來看圖解。
圖解
我以 listA = [0, 9, 1, 2, 4]、listB = [3, 2, 4] 為例，相交節(jié)點(diǎn)的值為 2。
指向 listA 和 listB 的指針分別為 flagA 和 flagB，兩個鏈表的長度分別用 lenA 和 lenB 表示。
首先初始化兩個指針和鏈表長度。
# 初始化headA、headB的指針和長度flagA, flagB = headA, headBlenA, lenB = 0, 0
然后計(jì)算兩個鏈表長度的差值
# 求鏈表 A 的長度while flagA:flagA = flagA.next= 1# 求鏈表 B 的長度while flagB:flagB = flagB.nextlenB += 1
在本例中，鏈表 A 比鏈表 B 長，差值為 2，所以鏈表 B 的指針 flagB 移動差值的距離。
# 當(dāng)A是長鏈表，則指針flagA后移到和B鏈表同等長度的位置上。if lenA > lenB:d_value = lenA - lenBwhile d_value:flagA = flagA.nextd_value -= 1
之后 flagA 和 flagB 同時(shí)向后遍歷。
flagA = flagA.nextflagB = flagB.next
如果找到 flagA 和 flagB 指向相同，即相遇，則返回指針，否則繼續(xù)遍歷，直到兩個指針都指向 Null，表明沒有交點(diǎn)。
本例中相遇節(jié)點(diǎn)為 2。
if flagA == flagB:return flagA
我這個解法比起人家那個浪漫的確實(shí) low 了點(diǎn)，但是復(fù)雜度上完全不輸。
鏈表 headA 和 headB 各遍歷了一遍，時(shí)間復(fù)雜度同樣為 O(n + m)。
同時(shí)也沒整額外的存儲，空間復(fù)雜度為 O(1)。
我要驕傲了呀。
代碼實(shí)現(xiàn)
Python 代碼實(shí)現(xiàn)
為了讓大家看明白點(diǎn)，代碼我用了最簡單粗暴的形式寫的，一點(diǎn)炫技都沒加，保證能看懂。
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:# 鏈表A和B任一為空，鏈表不相交if not headA or not headB:return None# 初始化headA、headB的指針和長度flagB = headA, headBlenB = 0, 0# 求鏈表 A 的長度while flagA:flagA = flagA.nextlenA += 1# 求鏈表 B 的長度while flagB:flagB = flagB.nextlenB += 1# 重新指向表頭flagB = headA, headB# 為了讓大家看的明白點(diǎn)，我就不用華麗花哨的寫法了，用最笨的寫法表示。# 當(dāng)A是長鏈表，則指針flagA后移到和B鏈表同等長度的位置上。if lenA > lenB:d_value = lenA - lenBwhile d_value:flagA = flagA.nextd_value -= 1# 當(dāng)B是長鏈表，則指針flagB后移到和A鏈表同等長度的位置上。else:d_value = lenB - lenAwhile d_value:flagB = flagB.nextd_value -= 1# 然后兩個指針flagA和flagB同時(shí)遍歷while flagA:if flagA == flagB:return flagAelse:flagA = flagA.nextflagB = flagB.next# 如果沒有相遇，返回 Nonereturn None
Java 代碼實(shí)現(xiàn)
/*** 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在同一起點(diǎn)上（末尾位置對齊）while (gap-- > 0) {curA = curA.next;}// 遍歷curA 和 curB，遇到相同則直接返回while (curA != null) {if (curA == curB) {return curA;}curA = curA.next;curB = curB.next;}return null;}}
圖解相交鏈表到這就結(jié)束了，可算寫完了，差點(diǎn)寫的累死。
沒想到?jīng)]被題困住，差點(diǎn)被題意堵死。
道理明白了就好啦，重要的是解題思路，而不是題本身，這次講的這兩個思路都蠻有意思的，大家細(xì)細(xì)揣摩。