【图解 LeetCode】160：对不起，相交链表，我做的有点不浪漫。

逃离我推掉我的手 2022-09-11 04:19 158阅读 0赞

大家好呀，我是直男蛋。

今天来做**相交链表**，这道题本来是**难度简单**的水题，但是有两个奇怪点把我给整楞了。

一个就是题意，另一个就是解题方式，感觉直接把我的直男属性给暴露了。

具体的到下面细聊，现在先开始看题。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]

--------------------

## LeetCode 160：相交链表 ##

### 题意 ###

给出两个单链表的头节点，找出两个单链表相交的起始节点。

### 示例 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

### 提示 ###

题目保证不存在环。

len(listA) = m, len(listB) = n

0 <= m, n <= 3 \* 10^4

1 <= Node.val <= 10^5

0 <= skipA <= m, 0 <= skipB <= n

### 题目解析 ###

在说我的解法之前，我先来说一下文章开头我说的是啥意思。

这个题目一开始题意给我看楞了，不看示例，打眼看上去还以为是找数值相等的节点。

估计很多臭宝容易看懵，**这道题其实是找相交节点的指针**（即同一节点，引用完全相同），而不是单纯遍历找第一个数值相同的节点，这点大家要搞清楚。

光这个出题的题意，我感觉就得值个难度 hard！

![在这里插入图片描述][292a71cfe7ce4766821afeb61450f461.png_pic_center]  
其实搞清楚了题意，稍微一想解法就能出来。

在我劈里啪啦的敲完代码然后 AC 的时候，随意点开了力扣的题解区，官方的题解给我看楞了。

虽然用了双指针，但是它的解法楞是用上了数学的思想。

怕你们在做的时候会先去看题解，然后又看不懂别人怎么个思想，所以这里就给臭宝们讲一下**“浪漫”的做法**。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_16_color_FFFFFF_t_70_g_se_x_16_pic_center]  
官方的方法是：

*  链表 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)。

看了一下评论，浪漫气息弥漫：

> 错的人就算走过了对方的路也还是会错过。  
>   
> 走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

看到这我应该非常肯定自己是个废物了。

本应该拍手称快，但是这解法属实让我愣了：这还是一道简单题？

我感觉我等凡人，不在草稿纸上划拉划拉，一下子也看不懂它的题解是什么意思，更不用说在面试或者比赛中想出这样的解法了。

好了，这个解法就说到这吧。

下面，该是本直男蛋的做法了，比起人家的解法我这简直是俗不可耐，但保证看一眼就能看明白。

我也用到了双指针，不过我是从屁股开始的。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_10_color_FFFFFF_t_70_g_se_x_16_pic_center]  
你想，**如果两个链表相交的话，那必定有一段公共段**。

既然有这个前提，那公共段以前的对比那是白送的无用功。

**让长链表先走“两个链表长度的差值”，然后链表从长度相同的位置开始同步向后遍历。**

**找到相交节点，则返回节点，如果没相交节点的话，两个指针都指向 Null。**

光这么说可能不好理解，下面来看图解。

### 图解 ###

我以 listA = \[0, 9, 1, 2, 4\]、listB = \[3, 2, 4\] 为例，相交节点的值为 2。

指向 listA 和 listB 的指针分别为 flagA 和 flagB，两个链表的长度分别用 lenA 和 lenB 表示。

首先初始化两个指针和链表长度。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

# 初始化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 移动差值的距离。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]

# 当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。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]

if flagA == flagB:
          return flagA

我这个解法比起人家那个浪漫的确实 low 了点，但是复杂度上完全不输。

链表 headA 和 headB 各遍历了一遍，**时间复杂度同样为 O(n + m)**。

同时也没整额外的存储，**空间复杂度为 O(1)**。

我要骄傲了呀。

![在这里插入图片描述][81cf4427d31649b8a3859f0639588ec5.png_pic_center]

## 代码实现 ##

### 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;
        }
        
    }

--------------------

**图解相交链表**到这就结束了，可算写完了，差点写的累死。

没想到没被题困住，差点被题意堵死。

道理明白了就好啦，**重要的是解题思路，而不是题本身**，这次讲的这两个思路都蛮有意思的，大家细细揣摩。

揣摩之前先**点赞在看**，养成好习惯，有问题留言区见。

我是蛋蛋，我们下次见！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_18_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/b7ca044248154d328f85c97b8a99c402.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/6498b27578b84625bff593b0056d7579.png
[292a71cfe7ce4766821afeb61450f461.png_pic_center]: /images/20220828/343178e9b227400ea0126b90f60c36bf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_16_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/6ef9b25d62b3426fb3942b4cc1739cd0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_10_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/b2f5ca225a894274ab78875f5e8cc7c9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220828/c351688ab74e448f94790d141dbe75e1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20220828/1eb89b94565340fdaea2537f2b76fdc4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUm9ja3kwNDI5_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]: /images/20220828/22c987402bf142738d5baf42cab50aca.png
[81cf4427d31649b8a3859f0639588ec5.png_pic_center]: /images/20220828/6cbf2bd93c9449d0a5f33010b1728846.png