[每日一题] 第二题:反转链表

题目描述

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

限制:

0 <= 节点个数 <= 5000

题解

利用外部空间

先申请一个动态扩容的数组或者容器,比如 ArrayList这样的,

然后不断遍历链表,将链表中的元素添加到这个容器中。

再利用容器自身的 API,反转整个容器,这样就达到反转的效果了。

最后同时遍历容器和链表,将链表的值改为容器的值。

因为此时容器的值为 5 4 3 2 1

链表按照这个顺序重新被设置一遍,就达到要求了。

空间复杂度

O(N)

双指针法

算法思想

我们申请两个指针,一个指针叫 pre,最初指向 NULL。

第二个指针 cur 指向 head,然后不断遍历 cur

每次迭代 cur,都将 curnext 指向 pre,然后 precur 前进一位。

都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        //申请节点,pre和 cur,pre指向null
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur!=null) {
            //记录当前节点的下一个节点
            tmp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;
            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

个人理解

从头遍历链表,修改每个节点的 next 指向的值。

那么一个节点的新的 next 值是什么呢,是它的前一个节点,那么我们把它保存起来即可,用的时候再取出来该值,所以我们定义了 pre 节点。

那么我们应该什么时候给当前节点的 next 节点赋值呢?

我们不能直接执行下面的代码 head.next = pre;,这样是不可以的,形成闭环了。

所以我们有个临时变量 tmp,用来存储当前节点的 next 的值,首先将 head.next 值取出来,然后将 head.next 赋值为 pre,再将 tmp 值赋值给 head,这样我们就下一层循环了。最终获取最后一个节点,就是反转链表的第一个节点,那能否通过 head 节点获取这最后一集个节点呢,因为我们的 head 节点是最后一个节点的 next 值,为 null,所以我们取 head.pre 的值就可以了。

上面的代码用 cur 来代替 head

递归法

算法思想

递归的两个条件:

  1. 终止条件是当前节点或者下一个节点==null

  2. 在函数内部,改变节点的指向,也就是 head 的下一个节点指向 head 递归函数那句


head.next.next = head

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空,或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5,那么此时的cur就是5
        //而head是4,head的下一个是5,下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环,需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur,也就是最后一个节点
        return cur;
    }
}

个人理解

终止条件为什么有两个?

分别对应着两种情况:

  1. 链表为空,需要判断 head==null
  2. 正常链表,需要判断 head.next==null

head.next.next = head 怎么理解?**

head.next 是当前节点的下一个节点,这个节点的 next 值就是反过来嘛,就是 head

head.next = null 是什么意思?**

为了防止闭环。

为什么会返回 cur?

因为 cur 是最后一层递归返回的值,也就是最后一个节点,也是反转链表的第一个节点,所以我们返回这个节点即可。

题目出处

作者:wang_ni_ma
链接:leetcode-cn.com/problems/fan-zhuan...
来源:力扣(LeetCode)

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!