首页 > Top面试题-反转链表的两种解法
头像
蘑菇睡不着
编辑于 2021-08-03 18:07
+ 关注

Top面试题-反转链表的两种解法

一、题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
比如:原先链表是这样:

反转之后是这样:

二、思路分析:

方法一:迭代

反转链表就是将每个节点的 -> 指向这个节点的前一个节点。咱先不想代码怎么写,就以上面的图为例,比如以 “2” 这个节点(为了更好理解,假设“1”节点已经反转完毕)为例,我想反转这个节点该咋做?是不是主要三步走:

  1. 找到 当前节点,也就是被反转的节点,这里假设是 “2” 这个节点。
  2. 我们不是要指向前一个节点嘛,那我需要确定找到 当前节点前置节点,然后将当前节点的 next 指向前一个节点。
  3. 其实到这里当前节点的反转已经完毕了,但因为我们已经将当前节点的 next 指向前置节点了,所以和下一个节点就没有连接了,这会导致下一个节点在反转的时候找不到前置节点,所以我们要把当前节点的下一个节点(也就是后置节点)保存下来,以供后置节点来反转,并且会把“后置节点”继续当作“当前节点”来重复这个动作,直到结束。

AC代码

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode node = head;
        // 用于当作每个节点的前一个节点
        ListNode prev = null;

        while (node != null) {
            // 先存储每当前点的下一个节点 
            ListNode next = node.next;
            // 将当前节点的 next 指针指向前一个节点
            node.next = prev;
            // 将当前节点作为下一个节点的前置节点
            prev = node;
            // 将 后置节点 继续当作 当前节点来重复这个动作
            node = next;
        }
        return prev;
    }
}

时间复杂度:O(n),其中 n 是链表的长度,要遍历一次链表
空间复杂度:O(1)。

方法二:递归

反转链表除了用上面迭代的思维做,还可以用递归来实现,相信大多数小伙伴会觉得递归稍微复杂一些,不好理解,其实我刚做的时候也是这么觉得,可是当我理解了这题的精髓之后发现递归远远要比迭代好理解的多,哈哈哈,你们也不用不信,接下来咱们好好剖析一下就知道了。
再讲之前和大家聊聊啥是递归,其实在网上是可以找到很多关于递归的解释的,不过在我这里我认为,递归就是对同一个节点做相同的操作,以此来处理某种场景。
图片说明
文字解说:
(1)先递归,递归到倒数第二个节点,因为倒数第一个节点是最后一个节点,没有next节点。
(2)此时来到了倒数第二个节点“3”,此时的目的就是将节点“3”和节点“4”中间的 “->” 变为 “<-”,这个也好弄,只需要将 节点“3” 的next节点“4”的next指针指向节点“3”本身就 OK 了,然后将 节点“3”的next指针指向 null 即可,至此,节点“3”的反转就完成了,是不是炒鸡简单!
(3)然后到了节点“2”,只需要重复节点“3”的动作即可,节点“1”也是如此。这样整个链表的反转就完事了,没骗你们吧,确实很简单滴。

接下来上代码!!!

AC 代码

public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 已经到最后一个节点了,返回 作为新链表的头节点
        if (head == null || head.next == null) {
            return head;
        }
        // 得到新链表的头节点,这个头节点上 head.next,head 是倒数第二个节点
        ListNode newHead = ReverseList(head.next);
        // 将倒数第二个节点 head 的 next 节点的 next 指针指向 head本身
        head.next.next = head;
        // 将 head 的next 指针指向 null,至此 head 节点就反转完了
        head.next = null;
        // 返回头节点,继续处理之前的节点
        return newHead;
    }
}

时间复杂度:O(n),其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度:O(n),其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间,最多为 n 层。

四、总结

还是更推荐第一种解法,相比第二题空间复杂度更低一些,这道题可是面试高频题呦,大家一定要会!!!

更多模拟面试

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐