Leetcode 反转链表系列 图解详细过程

in 网站建设
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

对于一个程序猿来说,数据结构和算法的重要性就不用我多说了吧,算法题已然成了现在大厂笔试面试的重头戏,废话少说,Leetcode 刷起来呀。说起刷 Leetcode,我建议你按 tag 刷,不然只能像无头苍蝇,东一榔头西一棒槌,最后事倍功半 (过来人的惨痛经历)。最近正好在刷 Leetcode 上的链表题,也碰到了一些颇具代表性的题型,正好做个记录,也分享给有需要的小伙伴。

对链表不太熟悉的小伙伴碰到链表问题可能会觉得无从下手,相比数组,链表确实会更加抽象,也需要一定的空间想象力,特别是一些指针戳来戳去,容易把人搞懵。这个时候你不妨拿出纸笔,画个简单的示意图,这对你解决链表问题非常有帮助。本篇文章将以图解的方式介绍三道链表反转的算法题,在 Leetcode 上分别对应简单、中等和困难的难度级别,算是比较有代表性的题型,对于解决链表问题很有参考意义。

1、 Leetcode 206 题 Reverse Linked List (难度:简单)

题目描述如下:

反转链表I题目描述

解法一、迭代反转

先来看示意图,以链表1->2->3->4->5为例:

单链表迭代反转示意图

单链表迭代反转示意图

在遍历链表时,每一次循环只需要做三件事,1. 把当前节点的 next 指针指向其前驱节点;2. 把前驱节点指针指向当前节点;3. 把当前节点指针指向其下一个节点。需要注意的是,我们需要一个变量来暂存当前节点的下一个节点,这里我们用 temp 表示,代码如下

public ListNode reverseList(ListNode head) {
    // 前驱节点初始为null
    ListNode prev = null;
    // 当前节点用cur表示
    ListNode cur = head;
    // 用temp暂存下一个节点
    ListNode temp;
    while (cur != null) {
        // 获取下一个节点
        temp = cur.next;
        // 把当前节点的 next 指针指向其前驱节点
        cur.next = prev;
        // 把前驱节点指针指向当前节点
        prev = cur;
        // 把当前节点指针指向其下一个节点
        cur = temp;
    }
    // 注意最后返回的是prev
    return prev;
}

解法二、递归反转

很多题目用递归都可以写出相当简洁的答案,不过相对于迭代,递归确实没那么好理解。本菜鸡至今也只会用递归解决一些相当基础的题目,比如本题。很多人在面对递归问题时都很容易陷入细节中无法自拔,但是再聪明的脑袋恐怕装不了几层递归栈,所以应该把重点放在子问题和结束条件上。这次先上代码再上图

public ListNode reverseList(ListNode head) {
        // 递归终止条件是当前节点为空,或者当前节点的下一个节点为空
        // 毫无疑问,在这道题中返回的就是单链表的尾节点
        if(head == null || head.next==null) {
            return head;
        }
        // 将当前节点之后的子链表反转任务交给子过程处理,不要陷入细节
        // 只需要知道子过程可以完成子链表的反转就够了
        ListNode p = reverseList(head.next);
        // 经过上面的反转,子链表已经反转完成,接下来要做的就是处理子链表和当前节点的关系
        // 下面两步配合示意图理解
        head.next.next = head;
        // 防止链表循环,需要将head.next置为空
        head.next = null;
        // 每一层递归函数返回的都是p,也就是初始链表的尾节点
        return p;
    }

假设链表是 1->2->3->4->5,下面是递归过程示意图。

单链表递归反转示意图

单链表递归反转示意图

下面再贴一个 Leetcode 本题讨论区的一个热评,希望可以帮助你理解递归过程。

不妨假设链表为1,2,3,4,5。按照递归,当执行reverseList(5)的时候返回了5这个节点,reverseList(4)中的p就是5这个节点,我们看看reverseList(4)接下来执行完之后,5->next = 4, 4->next = null。这时候返回了p这个节点,也就是链表5->4->null,接下来执行reverseList(3),代码解析为4->next = 3,3->next = null,这个时候p就变成了,5->4->3->null, reverseList(2), reverseList(1)依次类推,p就是:5->4->3->2->1->null。

2、Leetcode 92题 Reverse Linked List II (难度:中等)

题目描述如下:

翻转链表II题目描述

解析:本题,还有下一个要介绍的困难级别的题目,算是一种类型题,它们都是要对链表中特定区间中的节点进行操作。面对这种题目,有固定的套路可以帮你简化解题思路,套路如下:

  1. 给链表添加虚拟头节点 dummy,这样就不需要再单独考虑头节点了,可以省去很多麻烦;
  2. 找到需要操作的链表区间,区间起始节点用 start 表示,结束节点用 end 表示;
  3. 对区间上的链表进行操作;
  4. 将操作后的链表重新接回原链表,这里我们需要另外两个变量,前驱节点 prev 和后继节点 successor。

这样,我们就完成了所有操作,返回 dummy.next 即可,示意图如下

单链表区间反转示意图

单链表区间反转示意图

然后上代码:

public ListNode reverseBetween(ListNode head, int m, int n) {
    // 添加虚拟头节点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    // 前驱节点
    ListNode prev = dummy;
    // 反转区间开始节点
    ListNode start = head;
    // 反转区间结束节点
    ListNode end = head;
    // 后继节点
    ListNode successor;
    // 第一个for循环可以找到前驱节点和区间开始节点
    for (int i = 1; i < m; i++) {
        prev = prev.next;
        start = start.next;
        end = end.next;
    }
    // 第二个for循环可以找到区间结束节点
    for (int i = m; i < n; i++) {
        end = end.next;
    }
    // 找到后继节点
    successor = end.next;
    // 至关重要的一步,将反转区间的最后一个节点和原链表断开,否则会造成死循环
    end.next = null;
    // 将反转后的头节点连在前驱结点后面,这里的 reverseList() 方法直接复用上一题的翻转单链表方法即可
    prev.next = reverseList(start);
    // 反转后,start变成尾结点,把它和后继结点连接起来
    start.next = successor;
    return dummy.next;
}

3、Leetcode 25题 K 个一组翻转链表(难度:困难)

题目描述如下:

K个一组反转链表题目描述

解析:本题与上一题有很大的相似之处,都是对区间上的链表进行操作,不同的是本题需要连续对多个区间进行操作,看似无从下手,其实只比上一题多了个循环的过程,过程如下图所示:

K个一组反转链表示意图

K个一组反转链表示意图

代码如下:

public ListNode reverseKGroup(ListNode head, int k) {
    // 添加虚拟头结点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    ListNode start = head;
    ListNode end = head;
    ListNode successor;
    while (end != null) {
        // 循环k次,确定待反转区间
        for (int i = 1; i < k && end != null; i++) {
            end = end.next;
        }
        // end节点为空的话说明待反转节点不足k个,直接返回
        if (end == null) {
            break;
        }
        successor = end.next;
        //至关重要的一步,将待反转链表的最后一个节点和后续链表断开
        end.next = null;
        // 进行反转链表操作,并将反转后的链表头结点连接在prev之后
        // 这里的 reverseList() 方法直接复用第一题的翻转单链表方法即可
        prev.next = reverseList(start);
        // start在反转后会变成尾结点,将其与successor连接起来
        start.next = successor;
        // 以下对各变量重新赋值,然后进行下一次循环
        prev = start;
        start = successor;
        end = successor;
    }
    return dummy.next;
}

4、总结

来来来再总结一下,很多链表题都可以通过添加虚拟头结点来简化解题思路,对于区间操作的情况,可以考虑使用前驱、后继、开始和结束等变量,另外就是要多动笔画画,毕竟眼睛看到的会更加直观。

艾玛终于掰扯完了,这些图真是画得我身心俱疲,就当是做个笔记加深印象吧,也希望可以帮到有需要的小伙伴。

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看