侧边栏壁纸
博主头像
王一川博主等级

努力成为一个不会前端的全栈工程师

  • 累计撰写 69 篇文章
  • 累计创建 20 个标签
  • 累计收到 38 条评论

目 录CONTENT

文章目录

链表反转

王一川
2023-07-25 / 0 评论 / 0 点赞 / 1,766 阅读 / 1,780 字
温馨提示:
本文最后更新于 2023-07-25,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一、定义链表

这里定义带哨兵的链表

package linkedlist;

// 反转链表的五种方式
public class ReverseLinkedList {
    private final Node head = new Node(null, null);

    // 快速填充链表
    public void fill() {
        Node n5 = new Node(5, null);
        Node n4 = new Node(4, n5);
        Node n3 = new Node(3, n4);
        Node n2 = new Node(2, n3);
        head.next = new Node(1, n2);
    }

    // 打印链表
    public void display() {
        Node p = head.next;
        while (p != null) {
            System.out.print(p.value + " -> ");
            p = p.next;
        }
    }

    private static class Node {
        private final Object value;
        private Node next;

        public Node(Object value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ReverseLinkedList linkedList = new ReverseLinkedList();
        linkedList.fill();
        linkedList.display();
    }
}

二、反转链表

2.1 方式一

创建一个新的链表,依次遍历老的链表获取的元素插入到新链表首位

public ReverseLinkedList reverse1() {
    // 创建新的链表
    ReverseLinkedList newList = new ReverseLinkedList();
    // 遍历当前链表
    Node p = head.next;
    while (p != null) {
        // 首插法
        newList.head.next = new Node(p.value, newList.head.next);
        p = p.next;
    }
    return newList;
}

下面用图解释一下newList.head.next = new Node(p.value, newList.head.next);是如何实现将元素插入头部

对于 new Node(p.value, newList.head.next) 图示如下

image-20230724203555450

最后 newList.head.next = new

image-20230724203621654

2.2 方式二

方式一的缺点就是每一个节点都需要重新创建,空间复杂度较高。

因此方式二对这点进行优化,其基本思路依然是遍历,只不过是依次移除原链表的每个节点并将其插入到新链表的头部,下面是将一个 node 节点添加到链表头部

public void addFirst(Node node) {
    node.next = head.next;
    head.next = node;
}

下面是移除链表头部元素

public Node removeFirst() {
    // 保存第一个元素
    Node p = head.next;
    // 判空
    if (p != null) {
        // 移除第一个元素
        head.next = head.next.next;
    }
    return p;
}

因此方式二的方式如下

public ReverseLinkedList reverse2() {
    ReverseLinkedList newList = new ReverseLinkedList();
    // 依次移除链表元素
    Node node = removeFirst();
    while (node != null) {
        newList.addFirst(node);
        node = removeFirst();
    }

    return newList;
}

2.3 方式三

方式二依然是创建了新的链表对象,只不过没有创建新的节点对象,有没有一种方式是在原链表的基础上直接进行反转?首先我们实现通过递归方式找到链表的最后一个节点

public void test() {
    System.out.println(recursion(head.next).value);
}

private Node recursion(Node node) {
    if (node == null || node.next == null) {
        return node; // 最后一个节点
    }
    return recursion(node.next);
}

递归调用实例图如下:

image-20230725091729260

上述递归我们发现

当 node = 4 时,此时 node -> 4; node.next -> 5,不看其他节点只将 5 -> 4,那么此刻的指向时 5 -> 4; 4 -> 5

当 node = 3 时,此时 node -> 3; node.next -> 4,不看其他节点只将 4 -> 3,那么此刻的指向时 5 -> 4; 4 -> 3; 3 -> 4

当 node = 2 时,此时 node -> 2; node.next -> 3,不看其他节点只将 3 -> 2,那么此刻的指向时 5 -> 4; 4 -> 3; 3 -> 2; 2 -> 3

当 node = 1 时,此时 node -> 1; node.next -> 2,不看其他节点只将 2 -> 1,那么此刻的指向时 5 -> 4; 4 -> 3; 3 -> 2; 2 -> 1; 1 -> 2

看起来似乎是反转了链表,但细心的同学或许发现问题所在,就是每层递归结束后的节点指向存在循环引用的风险,且最后一次递归应该指向 null,所以我们在交换指针指向时多做一步,例如

当 node = 4,我们需要将 5 -> 4 同时将 4 -> null 即可,代码如下

private Node recursion(Node node) {
    if (node == null || node.next == null) {
        return node; // 最后一个节点
    }
    Node recursion = recursion(node.next);
    node.next.next = node;
    node.next = null;
    return recursion;
}

ReverseLinkedList 作为对 Node 的封装同时携带一个哨兵节点,那么我们只需要在方法结束获取返回值时,将 head 指向该返回值即可,因此方法三代码如下:

public void reverse3() {
    head.next = recursion(head.next);
}

2.4 方法四

其思路和方法二类似,区别在于该方法是在原链表上面直接操作指向实现反转,思路如下:

step-1: 定义三个指针,n1 始终指向链表第一个节点,o1 初始状态指向链表第一个节点,o2 始终指向 o1 的下一个节点

image-20230725095049068

step-2: 断开 o2 指向的节点,即o1.next = o2.next

image-20230725095204135

step-3: 将 o2 链入到链表头部,即o2.next = n1

image-20230725095309992

step-4: 此时已完成1、2节点的反转,下面需要让 n1 和 o2 回归原本语义,即 n1 始终指向链表头部,那么o1 = o2;o2 始终指向 o1 的下一个节点,那么o2 = o1.next

image-20230725095540600

step-5: 重复 step-2 直到 o2 = null

代码实现如下:

public void reverse4() {
    // step-1: 定义三个指针,n1 始终指向链表第一个节点,o1 初始状态指向链表第一个节点,o2 始终指向 o1 的下一个节点
    Node n1 = head.next;
    Node o1 = head.next;
    if (o1 == null) {
        // 空链表
        return;
    }
    Node o2 = o1.next;
    // step-5: 重复 step-2 直到 o2 = null
    while (o2 != null) {
        // step-2: 断开 o2 指向的节点
        o1.next = o2.next;
        // step-3: 将 o2 链入到链表头部
        o2.next = n1;
        // step-4: 此时已完成1、2节点的反转,下面需要让 n1 和 o2 回归原本语义
        n1 = o2;
        o2 = o1.next;
    }
    // 改变 head 指向
    head.next = n1;
}

2.5 方法五

方法五是对方法二的重构,思路就是循环老链表每个节点依次插入到新的链表头部,区别在于方法二是面向对象,而方法五是面向过程,相较于此代码量和可读性将进一步提高,思路如下

step-1: 定义两个指针,o1 始终指向老链表头部,n1 始终指向新链表头部,初始为 null

image-20230725101700447

step-2: 先定义一个辅助节点 o2 指向 o1 的下一个节点,然后将 o1 指向的节点链入 n1 新链表的头部。o2 的作用是让 o1 能回归原本的语言(当然用 head 回去也是一样的,只不过要平凡动 head)

image-20230725102134311

step-3: n1、o1 归位,即 n1 始终指向新链表头部,o1 始终指向老链表头部,这里 o1 需要借助 o2 才能归为

image-20230725102306703

step-4: 如果 o1 不指向 null 则回到 step-2,否则结束

代码实现如下:

public void reverse5() {
    // step-1: 定义两个指针,o1 始终指向老链表头部,n1 始终指向新链表头部,初始为 null
    Node o1 = head.next;
    Node n1 = null;
    // step-4: 如果 o1 不指向 null 则回到 step-2,否则结束
    while (o1 != null) {
        // step-2: 先定义一个辅助节点 o2 指向 o1 的下一个节点,然后将 o1 指向的节点链入 n1 新链表的头部
        Node o2 = o1.next;
        o1.next = n1;
        // step-3: n1、o1 归位,即 n1 始终指向新链表头部,o1 始终指向老链表头部
        n1 = o1;
        o1 = o2;
    }
    // 改变 head 指向
    head.next = n1;
}
0

评论区