首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >单链表的六大解题套路,你都见过么?

单链表的六大解题套路,你都见过么?

作者头像
labuladong
发布2021-09-23 11:37:45
2600
发布2021-09-23 11:37:45
举报

读完本文,可以去力扣解决如下题目:

21. 合并两个有序链表(简单)

23. 合并K个升序链表(困难)

141. 环形链表(简单)

142. 环形链表 II(中等)

876. 链表的中间结点(简单)

160. 相交链表(简单)

19. 删除链表的倒数第 N 个结点(中等)

上次在视频号直播,跟大家说到单链表有很多巧妙的操作,本文就总结一下单链表的基本技巧,每个技巧都对应着至少一道算法题:

1、合并两个有序链表

2、合并k个有序链表

3、寻找单链表的倒数第k个节点

4、寻找单链表的中点

5、判断单链表是否包含环并找出环起点

6、判断两个单链表是否相交并找出交点

这些解法都用到了双指针技巧,所以说对于单链表相关的题目,双指针的运用是非常广泛的,下面我们就来一个一个看。

合并两个有序链表

这是最基本的链表技巧,力扣第 21 题「合并两个有序链表」就是这个问题:

给你输入两个有序链表,请你把他俩合并成一个新的有序链表,函数签名如下:

ListNode mergeTwoLists(ListNode l1, ListNode l2);

这题比较简单,我们直接看解法:

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;

    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }

    if (p1 != null) {
        p.next = p1;
    }

    if (p2 != null) {
        p.next = p2;
    }

    return dummy.next;
}

我们的 while 循环每次比较p1p2的大小,把较小的节点接到结果链表上:

这个算法的逻辑类似于「拉拉链」,l1, l2类似于拉链两侧的锯齿,指针p就好像拉链的拉索,将两个有序链表合并。

代码中还用到一个链表的算法题中是很常见的「虚拟头节点」技巧,也就是dummy节点。你可以试试,如果不使用dummy虚拟节点,代码会复杂很多,而有了dummy节点这个占位符,可以避免处理空指针的情况,降低代码的复杂性。

合并 k 个有序链表

看下力扣第 23 题「合并K个升序链表」:

函数签名如下:

ListNode mergeKLists(ListNode[] lists);

合并k个有序链表的逻辑类似合并两个有序链表,难点在于,如何快速得到k个节点中的最小节点,接到结果链表上?

这里我们就要用到 优先级队列(二叉堆) 这种数据结构,把链表节点放入一个最小堆,就可以每次获得k个节点中的最小节点:

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列,最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点,接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

这个算法是面试常考题,它的时间复杂度是多少呢?

优先队列pq中的元素个数最多是k,所以一次poll或者add方法的时间复杂度是O(logk);所有的链表节点都会被加入和弹出pq所以算法整体的时间复杂度是O(Nlogk),其中k是链表的条数,N是这些链表的节点总数

单链表的倒数第 k 个节点

从前往后寻找单链表的第k个节点很简单,一个 for 循环遍历过去就找到了,但是如何寻找从后往前数的第k个节点呢?

那你可能说,假设链表有n个节点,倒数第k个节点就是正数第n - k个节点,不也是一个 for 循环的事儿吗?

是的,但是算法题一般只给你一个ListNode头结点代表一条单链表,你不能直接得出这条链表的长度n,而需要先遍历一遍链表算出n的值,然后再遍历链表计算第n - k个节点。

也就是说,这个解法需要遍历两次链表才能得到出倒数第k个节点。

那么,我们能不能只遍历一次链表,就算出倒数第k个节点?可以做到的,如果是面试问到这道题,面试官肯定也是希望你给出只需遍历一次链表的解法。

这个解法就比较巧妙了,假设k = 2,思路如下:

首先,我们先让一个指针p1指向链表的头节点head,然后走k步:

现在的p1,只要再走n - k步,就能走到链表末尾的空指针了对吧?

趁这个时候,再用一个指针p2指向链表头节点head

接下来就很显然了,让p1p2同时向前走,p1走到链表末尾的空指针时走了n - k步,p2也走了n - k步,也就恰好到达了链表的倒数第k个节点:

这样,只遍历了一次链表,就获得了倒数第k个节点p2

上述逻辑的代码如下:

// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k 个节点
    return p2;
}

当然,如果用 big O 表示法来计算时间复杂度,无论遍历一次链表和遍历两次链表的时间复杂度都是O(N),但上述这个算法更有技巧性。

很多链表相关的算法题都会用到这个技巧,比如说力扣第 19 题「删除链表的倒数第 N 个结点」:

我们直接看解法代码:

// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟头节点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个,要先找倒数第 n + 1 个节点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}

private ListNode findFromEnd(ListNode head, int k) {
    // 代码见上文
}

这个逻辑就很简单了,要删除倒数第n个节点,就得获得倒数第n + 1个节点的引用,可以用我们实现的findFromEnd来操作。

不过注意我们又使用了虚拟头结点的技巧,也是为了防止出现空指针的情况,比如说链表总共有 5 个节点,题目就让你删除倒数第 5 个节点,也就是第一个节点,那按照算法逻辑,应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了,这就会出错。

但有了我们虚拟节点dummy的存在,就避免了这个问题,能够对这种情况进行正确的删除。

单链表的中点

力扣第 876 题「链表的中间结点」就是这个题目,问题的关键也在于我们无法直接得到单链表的长度n,常规方法也是先遍历链表计算n,再遍历一次得到第n / 2个节点,也就是中间节点。

如果想一次遍历就得到中间节点,也需要耍点小聪明,使用「快慢指针」的技巧:

我们让两个指针slowfast分别指向链表头结点head

每当慢指针slow前进一步,快指针fast就前进两步,这样,当fast走到链表末尾时,slow就指向了链表中点

上述思路的代码实现如下:

ListNode middleNode(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步,快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}

需要注意的是,如果链表长度为偶数,也就是说中点有两个的时候,我们这个解法返回的节点是靠后的那个节点。

另外,这段代码稍加修改就可以直接用到判断链表成环的算法题上。

判断链表是否包含环

判断单链表是否包含环属于经典问题了,解决方案也是用快慢指针:

每当慢指针slow前进一步,快指针fast就前进两步。

如果fast最终遇到空指针,说明链表中没有环;如果fast最终和slow相遇,那肯定是fast超过了slow一圈,说明链表中含有环。

只需要把寻找链表中点的代码稍加修改就行了:

boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步,快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇,说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

当然,这个问题还有进阶版:如果链表中含有环,如何计算这个环的起点?

这里简单提一下解法:

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    // 重新指向头结点
    slow = head;
    // 快慢指针同步前进,相交点就是环起点
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

可以看到,当快慢指针相遇时,让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置。

我们假设快慢指针相遇时,慢指针slow走了k步,那么快指针fast一定走了2k步:

fast一定比slow多走了k步,这多走的k步其实就是fast指针在环里转圈圈,所以k的值就是环长度的「整数倍」

假设相遇点距环的起点的距离为m,那么结合上图的 slow 指针,环的起点距头结点head的距离为k - m,也就是说如果从head前进k - m步就能到达环起点。

巧的是,如果从相遇点继续前进k - m步,也恰好到达环起点。因为结合上图的 fast 指针,从相遇点开始走k步可以转回到相遇点,那走k - m步肯定就走到环起点了:

所以,只要我们把快慢指针中的任一个重新指向head,然后两个指针同速前进,k - m步后一定会相遇,相遇之处就是环的起点了。

两个链表是否相交

这个问题有意思,也是力扣第 160 题「相交链表」函数签名如下:

ListNode getIntersectionNode(ListNode headA, ListNode headB);

给你输入两个链表的头结点headAheadB,这两个链表可能存在相交。

如果相交,你的算法应该返回相交的那个节点;如果没相交,则返回 null。

比如题目给我们举的例子,如果输入的两个链表如下图:

那么我们的算法应该返回c1这个节点。

这个题直接的想法可能是用HashSet记录一个链表的所有节点,然后和另一条链表对比,但这就需要额外的空间。

如果不用额外的空间,只使用两个指针,你如何做呢?

难点在于,由于两条链表的长度可能不同,两条链表之间的节点无法对应:

如果用两个指针p1p2分别在两条链表上前进,并不能同时走到公共节点,也就无法得到相交节点c1

所以,解决这个问题的关键是,通过某些方式,让p1p2能够同时到达相交节点c1

所以,我们可以让p1遍历完链表A之后开始遍历链表B,让p2遍历完链表B之后开始遍历链表A,这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接,就可以让p1p2同时进入公共部分,也就是同时到达相交节点c1

那你可能会问,如果说两个链表没有相交点,是否能够正确的返回 null 呢?

这个逻辑可以覆盖这种情况的,相当于c1节点是 null 空指针嘛,可以正确返回 null。

按照这个思路,可以写出如下代码:

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点,p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步,如果走到 A 链表末尾,转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步,如果走到 B 链表末尾,转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

这样,这道题就解决了,空间复杂度为O(1),时间复杂度为O(N)

以上就是单链表的所有技巧,希望对你有启发。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-08-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 labuladong 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 读完本文,可以去力扣解决如下题目:
    • 合并两个有序链表
      • 合并 k 个有序链表
        • 单链表的倒数第 k 个节点
          • 单链表的中点
            • 判断链表是否包含环
              • 两个链表是否相交
              相关产品与服务
              云直播
              云直播(Cloud Streaming Services,CSS)为您提供极速、稳定、专业的云端直播处理服务,根据业务的不同直播场景需求,云直播提供了标准直播、快直播、云导播台三种服务,分别针对大规模实时观看、超低延时直播、便捷云端导播的场景,配合腾讯云视立方·直播 SDK,为您提供一站式的音视频直播解决方案。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档