2021 后端开发笔记 22 链表基础练习题

单链表和双链表的翻转

链表的属于非常基础的数据结构，但是想要完成好它需要大量的练习，才能够在面试中不慌不乱的写好。

先分享今天听到的一个理论，来自《考试脑科学这本书》中：书中阐述了关于如何将普通的记忆转换成长期记忆。长期记忆的管理员是一个叫海马体的东西，由这个管理员来判断这个记忆是否值得放进长期记忆存储区域。那这个管理员判断的标准是什么呢？

标准是这个东西跟生活的危险有没有关系，你只要被开水壶烫过一次你就会永远记住不能摸开水壶。那么跟生活危险没关系的知识想要进入长期存储区怎么办？那只能去欺骗海马体了。。想要欺骗它你需要的重复练习，一直在管理员面前转悠，这时候管理员就会在想，这人是不是真的有事啊？要不要放它进去？进去了长期记忆就形成了。

还有一个方法，将自己置于对自己稍微不利的境地（当然这里指的是不太严重的！！），比如说肚子饿的时候，这时候海马体就会把你和危险联系起来，这时候就是背东西的最好时机了！冲冲冲

接下来开始看单链表翻转的练习

首先我们来看看单链表的翻转的代码，然后会画图来解释这个代码是怎么回事：

最简单的链表翻转当然是用java中的容器去做，将链表左右节点都放入容器中，然后反向遍历容器中的元素连接就行了，这样额外空间复杂度是 $O(n)$ 的，这里就不做代码阐述了。这里主要讲的是如何用额外空间复杂度 $O(1)$ 去翻转链表。

public class ReverseList {

    public static class Node { // 基本的链表节点声明
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    public static Node reverseLinkedList(Node head){
        Node pre = null;  // 记录 头节点的 前一个地方 的指针
        Node next = null; // 记录 头节点的 下一个要去的地方 的指针

        while(head != null){
            next = head.next; // 首先 先要记录好头节点的下一个地方，才不至于翻转之后不知道下一个地方要去哪
            head.next = pre; // 然后将 头节点的下一个地方 指向头节点的前一个地方
            pre = head; // 将 记录头节点的前一个地方的指针 移动到头指针的地方
            head = next; // 然后头指针也移动到下一个地方，循环往复直到头指针指向空处
        }
        return pre; // 记住我们要返回的是头指针前一个节点哦！因为头指针最终会指向空
    }
}

①：循环之前我们先准备好两个指针，一个是pre一个是next，pre指向的是head前面的一个节点！！
②：然后开始进入循环，循环的条件是head指向空就终止！！这时候我们先记录head的下一个环境，当head的指针往前指的时候我们就还能找到它下一个节点在哪。
③：这时候将head.next指向他的前一个环境，也就是pre。因为pre是空所以next就置为空了。
④：接下来我们需要做的就是将pre和head向前移动，所以第四歩就是将pre移动到head的位置。
⑤：将head移动到next的地方。

当head指向C的时候循环是不会判断为空的，所以这时候它还会进一次循环，然后指向空，所以最后一个循环的时候pre会指向C，所以我们最终会返回pre当成头节点。

注：图中有些地方画的不准确，为了方便理解。

图解代码流程

接下来是双向链表，代码和单链表一样，只多了一行，用来维护last的代码：

public class ReverseDoubleLinkedList {

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }

    public static DoubleNode reverseDoubleList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;

        while(head != null){
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }
}

Reference： https://italk.mashibing.com/course/detail/cour_00004003

2021 后端开发笔记 22 链表基础练习题

单链表 和 双链表的翻转

接下来开始看单链表翻转的练习

推荐阅读更多精彩内容

单链表和双链表的翻转