Grizzly's daily
0%

单链表解题技巧3——相交链表

发表于 更新于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

本文是关于单链表的判断相交问题，使用了两种方法，快慢指针和更好的逻辑连接方法。

涉及 leetcode 的 160. 相交链表。

相交链表

题目

首先来看题目160. 相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

示例1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

示例2：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

理解一下1

所谓链表相交，就是一个Y型的链表结构，在交点处汇流，需要注意的是:

链表相交后不会分开！因为链表只有一个next，只有唯一后继。

寻找两条链表相交的结点就是寻找相同的结点（而不是值！）

基本的思路是：

遍历第一条链表l1，嵌套遍历第二条链表l2，判断相同的结点即可。

这种方法的时间复杂度达到了O(n)不是很好，于是便思考其他方法。

  1. 我们需要找到相交点，而最后相交点之后链的长度都是一样的；
  2. 两个指针判断相等时需要同时到达相交点；
  3. 那么自然就需要使得前面遍历的经过的结点数相同；

解法一（双指针）

使用双指针来解决，我思考的时候还是比较自然的，表述可能不够清晰，自己动手比划比划就很清楚了。

  1. 当链长相同时，自然是一一比较即可（这种情况不用考虑，包含在下面）；
  2. 链长不同是，短链的指针l1会先到达终点，而长链指针l2则还有k个结点，这个k刚好是两条链的长度之差；
  3. 由此我们长链中再设一个指针llong，跟随l2继续前进;
  4. 当l2到达终点时，llong距离链尾刚好与短链长度相同；
  5. 此时在短链头设置一个指针lshort，与llong一同前进，一一比较即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *la = headA, *lb = headB;
    ListNode *lc, *llong, *lshort;
    // 依旧是快慢指针
    // la和lb同时前进
    while(la != nullptr && lb != nullptr){
        la = la->next;
        lb = lb->next;
    }
    // 选出长链和短链
    if(lb != nullptr){
        lc = lb;
        llong = headB;
        lshort = headA;
    }
    else{
        lc = la;
        llong = headA;
        lshort = headB;
    }
    // 指向长链的快指针带着慢指针走到头
    while(lc != nullptr){
        llong = llong->next;
        lc = lc->next;
    }
    //短链从头开始和后出发的慢指针同时前进即可找到相同点
    while(lshort != nullptr){
        if(lshort == llong){
            return llong;
        }
        lshort = lshort->next;
        llong = llong->next;
    }
    return nullptr;
}

解法二（逻辑连接）

继基本的分析思路，接下来要使得双指针同时到达交点：

  1. 只需要使得双指针在到达交点时经过相同个数的结点即可；
  2. 而我们知道A+B = B+A；
  3. 所以在A链前加上B链，在B链前加上A链，那么双指针同时从各自链出发，会在同一时刻到达相交点！
[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *la = headA, *lb = headB;
    while(la != lb){
        // A链完了去B链
        if (la != nullptr)
            la = la->next;
        else
            la = headB;
        // B链完了去A链
        if (lb != nullptr)
            lb = lb->next;
        else
            lb = headA;
    }
    return la;
}

个人收获

这次感觉自己有一点很好的使用了之前学过的双指针，毕竟学了会用才是真的学会了。

另外将两个链表逻辑连接，使得两个链表的长度相同，这一点还是很值得学习的，不能作为套路，但是是一个很好的思考方向。

------ 本文结束------