专栏首页WindCoder单链表反转Java版

单链表反转Java版

头插法与尾插法

本文主要用头插法实现单链表的反转,开始前先简单了解一下头插法与尾插法。

头插法:

在头节点的后面进行插入操作,后一个插入进来的值,在前一个插入进来的值与头节点之间。

尾插法:

设法找到插入结点的上一个结点,总而言之,尾插法就是要使后面插入的结点在前一个插入结点和NULL值之间。

链表反转

链表反转又可分为带逻辑头结点反转和不带逻辑头节点的反转,区别就是反转过程中是否单独设置一个逻辑头结点,具体可见代码。

设节点类为Node:

public static class Node{
    private int data;
    private Node next;

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public void setNext(Node next) {
         this.next = next;
    }

    public Node getNext() {
        return next;
    }
}

为方便阅读,之后不再调用Node的Setters/Getters函数,直接用其属性。

带逻辑头节点的反转

/**
* 输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
* @param head
* @return
*/
public static Node reverseList_head(Node head) {
    // 创建一个临时结点,当作头插法的逻辑头结点
    Node root = new Node(0, null);
    // 逻辑头结点点的下一个结点为空
    root.next = null;
    // 用于记录要处理的下一个结点
    Node next;
    // 当前处理的结点不为空
    while (head != null) {
        // 记录要处理的下一个结点
        next = head.next;
        // 当前结点的下一个结点指向逻辑头结点的下一个结点
        head.next = root.next;
        // 逻辑头结点的下一个结点指向当前处理的结点
        root.next = head;
        // 上面操作完成了一个结点的头插
        // 当前结点指向下一个要处理的结点
        head = next;
    }
    // 逻辑头结点的下一个结点就是返回后的头结点
    return root.next;
}

不带逻辑头节点的反转

该函数中不再有上面代码中开头创建的临时节点root。

/**
* 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
* @param list
* @return
*/
public Node reverseList(Node list){
    if (list == null || list.getNext() == null) return list;
    // 用于记录当前处理的结点的
    Node curre = list;
    // 用于记录当前结点的前驱结点
    // 前驱结点开始为null,因为反转后的最后一个结点的下一个结点,即null
    // 也是反转链表的头结点
    Node pre = null;
    // 当前结点的下一个结点
    Node next = null;
    // 对链表进行头插法操作
    while (curre!=null){
        // 记录要处理的下一个结点
        next = curre.next;
        // 当前结点的下一个结点指向前驱结点,这样当前结点就插入到了反转链表的头部
        curre.next = pre;
        // 记录当前结点为前驱结点,完成一次头插
        pre = curre;
        // 当前结点指向下一个要处理的结点
        curre = next;
    }
    return pre;
}

再略微修改一下,可减少一次循环,本质上没区别,仅是因为最后一个结点肯定是反转后的头结点,所以省掉了最后一次循环:

public Node inverseLinkList(Node list){
    if (list == null || list.next == null) return list;

    Node pre = null;
    Node curre = list;
    Node next = null;

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 函数出错返回的数据类型

    返回NULL值有各种弊端,对此有一个比较经典的应对策略,就是应用空对象设计模式(Null Object Design Pattern)。

    汐楓
  • 网易MySQL微专业学习笔记(八)-MySQL字符集

    这个系列属于个人学习网易云课堂MySQL数据库工程师微专业的相关课程过程中的笔记,本篇为其“MySQL数据库对象与应用”中的MySQL数据类型相关笔记。

    汐楓
  • 漫谈原型模式

    如果对象的创建成本比较大,而同一个类的不同对象之间差别不大(大部分字段都相同),在这种情况下,我们可以利用对已有对象(原型)进行复制(或者叫拷贝)的方式来创建新...

    汐楓
  • LinkedList源码详解

    秋白
  • Linkled List链表

    链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结...

    羊羽shine
  • Java 并发(1)AbstractQueuedSynchronizer 源码分析之概要分析

    链接 | http://www.cnblogs.com/liuyun1995/p/8400663.html

    一个优秀的废人
  • Hfish蜜罐搭建(docker&ubuntu)

    默认帐号密码均为:admin,如需修改可以通过加入-e USERNAME= -e PASSWORD= 传入环境变量进行修改。(也可以启动容器后,进入容器配置 c...

    释然
  • 通过域名获取主机IP -- struct addrinfo

    参考书籍:《UNIX环境高级编程》 (APUE,男神的书,出第三版了,有需要的私信我)

    看、未来
  • 氢能源的相关知识

    氢能源是一种二次能源,它是通过一定的技术利用其它能源而制取的,不像煤、石油和天然气等可以直接从地下开采、几乎完全依靠化石燃料。但是由于目前所用的煤、石油、天然气...

    用户5777378
  • Flutter大前端模式为开发者带来哪些机遇和挑战?

    在传统开发当中,有一个非常明显的现象 —— 基本都是基于自己的端进行开发,想跨端开发是非常难的。

    腾小云

扫码关注云+社区

领取腾讯云代金券