【Java数据结构和算法】004

2025-07-27 19:41:17

【Java数据结构和算法】004 0、警醒自己1、学习不用心，骗人又骗己；2、学习不刻苦，纸上画老虎；、学习不惜时，终得人耻笑；4、学习不复习，不如不学习；5、学习不休息，毁眼伤身体；6、狗才等着别人喂，狼都是自己寻食物；一、链表(Linked List)介绍1、概述链表是有序的列表；2、链表在内存中是存储如下、上图小结①链表是以节点的方式来存储，是链式存储；②每个节点包含 data 域（存

【Java数据结构和算法】004

0、警醒自己

1、学习不用心，骗人又骗己；

2、学习不刻苦，纸上画老虎；

、学习不惜时，终得人耻笑；

4、学习不复习，不如不学习；

5、学习不休息，毁眼伤身体；

6、狗才等着别人喂，狼都是自己寻食物；

一、链表(Linked List)介绍

1、概述

链表是有序的列表；

2、链表在内存中是存储如下

、上图小结

①链表是以节点的方式来存储，是链式存储；

②每个节点包含 data 域（存储实际值），next 域（指向下一个节点）；

③如图：发现链表的各个节点不一定是连续存储；

④链表分为带头节点的链表和不带头节点的链表，根据实际的需求来确定；

4、单链表(带头结点) 逻辑结构示意图

二、单链表的应用实例

1、单链表类属性内容

唯一ID + 类原始属性 + 下一个元素的ID；

（注意：我这里写的是下一个元素的ID，实际上代码演示的是下一个节点，其实本质没啥区别，但需要灵活理解！）

举例：

代码语言：javascript代码运行次数：0运行复制

public class Heroode{
    private int id;
    private String name;
    private String nickname;
    private int nextId;
}

2、添加元素

图解：

（备注：这里的nextId是另一种方式，代码演示中用的是next（下一个元素节点），其本质含义都是相通的，这里不再修改！）

说明：

先创建一个头节点“元素”，默认nextId为null，每添加一个元素，将上一个元素的nextId赋值为自己的id，将自己的nextId复制为null；

、遍历

从头结点拿到第一个元素的id，依次通过nextId获取下一个元素的id，直到nextId为null，链表结束，停止遍历；

4、代码演示

（链表 = 无限套娃！）

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

//测试单向链表
public class TestLinkedList {
    public static void main(String[] args) {
        //测试单链表
        SingleLinkedList list = new SingleLinkedList();
        //添加
        list.add(new Heroode(1,"宋江","及时雨"));
        list.add(new Heroode(2,"林冲","豹子头"));
        list.add(new Heroode(,"卢俊义","玉麒麟"));
        //遍历
        list.show();
    }
}
//定义一个单链表，来管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点，头节点不要动
    private final Heroode head = new Heroode(0,"","");
    //添加节点思路：首先到链表的最后一个节点，然后将此节点的nextId指向新节点
    public void add(Heroode heroode){
        Heroode temp = head;
        while ( != null) {
            //拿到下一个节点
            temp = ;
        }
        //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
         = heroode;
        println( +  + "添加成功！");
    }
    //遍历输出
    public void show(){
        Heroode temp = head;
        while ( != null){
            println( + );
            temp = ;
        }
        //上面走到最后一个节点的时候跑了，这里接着输出一下才行
        println( + );
    }
}
//英雄
class Heroode{
    final int id;
    final String name;
    final String nickname;
    Heroode next;

    public Heroode(int id, String name, String nickname) {
        this.id = id;
         = name;
         = nickname;
    }
}

5、运行结果

代码语言：javascript代码运行次数：0运行复制

及时雨宋江添加成功！
豹子头林冲添加成功！
玉麒麟卢俊义添加成功！

及时雨宋江
豹子头林冲
玉麒麟卢俊义

6、插入节点

图解：

（备注：这里的nextId是另一种方式，代码演示中用的是next（下一个元素节点），其本质含义都是相通的，这里不再修改！）

分析：

在中间插入一个id肯定是要给插入的位置的，比如将一个新的节点插入到id为2的节点之后，那么我们首先需要对链表进行遍历，到id为2的节点，然会进行相关操作即可，详见代码演示；

7、删除节点

图解：

（备注：这里的nextId是另一种方式，代码演示中用的是next（下一个元素节点），其本质含义都是相通的，这里不再修改！）

分析：

要删除一个节点，肯定是要给要删除节点的id，然后进行遍历查，在进行相关操作即可，详见代码演示；

8、代码演示

（在上面的代码基础上添加）

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

//测试单向链表
public class TestLinkedList {
    public static void main(String[] args) {
        //测试单链表
        SingleLinkedList list = new SingleLinkedList();
        //添加
        list.add(new Heroode(1,"宋江","及时雨"));
        list.add(new Heroode(2,"林冲","豹子头"));
        list.add(new Heroode(,"卢俊义","玉麒麟"));
        list.insert(2,new Heroode(4,"林冲之后","豹子头林冲之后"));
        list.remove(2);
        //遍历
        list.show();
    }
}
//定义一个单链表，来管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点，头节点不要动
    private final Heroode head = new Heroode(0,"","");

    //添加节点思路：首先到链表的最后一个节点，然后将此节点的nextId指向新节点
    public void add(Heroode heroode){
        Heroode temp = head;
        while ( != null) {
            //拿到下一个节点
            temp = ;
        }
        //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
         = heroode;
        println( +  + "添加成功！");
    }

    //指定一个节点的id，在其后面添加一个节点
    public void insert(int id, Heroode heroode){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        //跳出循环之后，就代表到了给定的id
        Heroode t = ;
         = heroode;
         = t;
        println( +  + "添加成功！");
    }

    //删除指定id的节点之后的那个节点
    //为什么不删除指定id的节点？因为单向链表只知道后面是谁，不知道前面是谁，也可以删除，
    // 但是需要再进行一次遍历，这里演示的是如何删除一个节点，所以不做过多纠结！
    public void remove(int id){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        println("移除了" + .nickname + .name);
        //这个时候，temp是要被删除的节点前面的那个节点
         = .next;
    }

    //遍历输出
    public void show(){
        Heroode temp = head;
        while ( != null){
            println( + );
            temp = ;
        }
        //上面走到最后一个节点的时候跑了，这里接着输出一下才行
        println( + );
    }
}

//英雄
class Heroode{
    final int id;
    final String name;
    final String nickname;
    Heroode next;

    public Heroode(int id, String name, String nickname) {
        this.id = id;
         = name;
         = nickname;
    }
}

9、运行结果

代码语言：javascript代码运行次数：0运行复制

及时雨宋江添加成功！
豹子头林冲添加成功！
玉麒麟卢俊义添加成功！
豹子头林冲之后林冲之后添加成功！
移除了豹子头林冲之后林冲之后

及时雨宋江
豹子头林冲
玉麒麟卢俊义

10、关于代码演示的说明

这里我们假定所给定的id是存在的，且所给定的新英雄的id不和其他id重复，否则再循环遍历的时候需要判断为空的、id已经存在，给定的id不存在、插入失败等情况；

我们也可以修改某一节点的内容，需要遍历到给定id对应的节点，再进行修改操作即可，与上面的代码区别不大，不再具体演示；

三、单链表面试题

1、求单链表中有效节点的个数

思路：

定义一个变量count=0，用来记录有效节点的个数；

直接遍历，每遍历一个count++，知道next==null，此时count即为有效节点的个数；

代码演示：

（在上面的基础上）

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

//测试单向链表
public class TestLinkedList {
    public static void main(String[] args) {
        //测试单链表
        SingleLinkedList list = new SingleLinkedList();
        //添加
        list.add(new Heroode(1,"宋江","及时雨"));
        list.add(new Heroode(2,"林冲","豹子头"));
        list.add(new Heroode(,"卢俊义","玉麒麟"));
        list.insert(2,new Heroode(4,"林冲之后","豹子头林冲之后"));
        list.remove(2);
        //遍历
        list.show();
        //输出有效节点个数
        println("有效节点个数：" + list.getum());
    }
}
//定义一个单链表，来管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点，头节点不要动
    private final Heroode head = new Heroode(0,"","");

    //添加节点思路：首先到链表的最后一个节点，然后将此节点的nextId指向新节点
    public void add(Heroode heroode){
        Heroode temp = head;
        while ( != null) {
            //拿到下一个节点
            temp = ;
        }
        //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
         = heroode;
        println( +  + "添加成功！");
    }

    //指定一个节点的id，在其后面添加一个节点
    public void insert(int id, Heroode heroode){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        //跳出循环之后，就代表到了给定的id
        Heroode t = ;
         = heroode;
         = t;
        println( +  + "添加成功！");
    }

    //删除指定id的节点之后的那个节点
    //为什么不删除指定id的节点？因为单向链表只知道后面是谁，不知道前面是谁，也可以删除，
    // 但是需要再进行一次遍历，这里演示的是如何删除一个节点，所以不做过多纠结！
    public void remove(int id){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        println("移除了" + .nickname + .name);
        //这个时候，temp是要被删除的节点前面的那个节点
         = .next;
    }

    //遍历输出
    public void show(){
        Heroode temp = head;
        while ( != null){
            println( + );
            temp = ;
        }
        //上面走到最后一个节点的时候跑了，这里接着输出一下才行
        println( + );
    }

    //获取有效节点的个数
    public int getum(){
        int count = 0;
        Heroode temp = head;
        while ( != null){
            temp = ;
            count++;
        }
        return count;
    }
}

//英雄
class Heroode{
    final int id;
    final String name;
    final String nickname;
    Heroode next;

    public Heroode(int id, String name, String nickname) {
        this.id = id;
         = name;
         = nickname;
    }
}

运行结果：

代码语言：javascript代码运行次数：0运行复制

及时雨宋江添加成功！
豹子头林冲添加成功！
玉麒麟卢俊义添加成功！
豹子头林冲之后林冲之后添加成功！
移除了豹子头林冲之后林冲之后

及时雨宋江
豹子头林冲
玉麒麟卢俊义
有效节点个数：

2、查单链表中的倒数第k个节点（新浪）

个人评述：

如果没有第1题，获取有效节点个数，这个题没那么简单就想到思路，既然上一个题已经得到了有效节点的个数count，那么这个问题就转化成了查单链表中的正数第count-k+1个节点了；

代码演示：

（在上面代码的基础上）

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

//测试单向链表
public class TestLinkedList {
    public static void main(String[] args) {
        //测试单链表
        SingleLinkedList list = new SingleLinkedList();
        //添加
        list.add(new Heroode(1,"宋江","及时雨"));
        list.add(new Heroode(2,"林冲","豹子头"));
        list.add(new Heroode(,"卢俊义","玉麒麟"));
        //再添加几个节点
        list.add(new Heroode(5,"吴用","智多星"));
        list.add(new Heroode(6,"公孙胜","入云龙"));
        list.add(new Heroode(7,"关胜","大刀"));
        list.insert(2,new Heroode(4,"林冲之后","豹子头林冲之后"));
        list.remove(2);
        //遍历
        list.show();
        //输出有效节点个数
        println("有效节点个数：" + list.getum());
        //倒数第个节点
        list.getK();
    }
}
//定义一个单链表，来管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点，头节点不要动
    private final Heroode head = new Heroode(0,"","");

    //添加节点思路：首先到链表的最后一个节点，然后将此节点的nextId指向新节点
    public void add(Heroode heroode){
        Heroode temp = head;
        while ( != null) {
            //拿到下一个节点
            temp = ;
        }
        //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
         = heroode;
        println( +  + "添加成功！");
    }

    //指定一个节点的id，在其后面添加一个节点
    public void insert(int id, Heroode heroode){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        //跳出循环之后，就代表到了给定的id
        Heroode t = ;
         = heroode;
         = t;
        println( +  + "添加成功！");
    }

    //删除指定id的节点之后的那个节点
    //为什么不删除指定id的节点？因为单向链表只知道后面是谁，不知道前面是谁，也可以删除，
    // 但是需要再进行一次遍历，这里演示的是如何删除一个节点，所以不做过多纠结！
    public void remove(int id){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        println("移除了" + .nickname + .name);
        //这个时候，temp是要被删除的节点前面的那个节点
         = .next;
    }

    //遍历输出
    public void show(){
        Heroode temp = head;
        while ( != null){
            println( + );
            temp = ;
        }
        //上面走到最后一个节点的时候跑了，这里接着输出一下才行
        println( + );
    }

    //获取有效节点的个数
    public int getum(){
        int count = 0;
        Heroode temp = head;
        while ( != null){
            temp = ;
            count++;
        }
        return count;
    }

    //获取倒数第k个节点
    public void getK(int k){
        int count = 0;
        int index = getum() - k + 1;
        Heroode temp = head;
        while (count != index){
            temp = ;
            count++;
        }
        //此时的temp就是要的节点
        println("倒数第" + k + "个节点为：" +  + );
    }
}

//英雄
class Heroode{
    final int id;
    final String name;
    final String nickname;
    Heroode next;

    public Heroode(int id, String name, String nickname) {
        this.id = id;
         = name;
         = nickname;
    }
}

运行结果：

代码语言：javascript代码运行次数：0运行复制

及时雨宋江添加成功！
豹子头林冲添加成功！
玉麒麟卢俊义添加成功！
智多星吴用添加成功！
入云龙公孙胜添加成功！
大刀关胜添加成功！
豹子头林冲之后林冲之后添加成功！
移除了豹子头林冲之后林冲之后

及时雨宋江
豹子头林冲
玉麒麟卢俊义
智多星吴用
入云龙公孙胜
大刀关胜
有效节点个数：6
倒数第个节点为：智多星吴用

、单链表的反转（腾讯）

说明：

单转意思就是把链表的顺序颠倒过来；

日志：

第一次写了很久总是出错，以致于当天感到些许的沮丧，没有继续，第二天一大早，思路清晰，几分钟写出来了，看来写代码之前、做事情之前需要清晰的思路；另一方面，如果思路不清晰的话，需要先理清思路，再开始做事情；

代码演示：

（在之前的基础上）

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

//测试单向链表
public class TestLinkedList {
    public static void main(String[] args) {
        //测试单链表
        SingleLinkedList list = new SingleLinkedList();
        //添加
        list.add(new Heroode(1,"宋江","及时雨"));
        list.add(new Heroode(2,"林冲","豹子头"));
        list.add(new Heroode(,"卢俊义","玉麒麟"));
        //再添加几个节点
        list.add(new Heroode(5,"吴用","智多星"));
        list.add(new Heroode(6,"公孙胜","入云龙"));
        list.add(new Heroode(7,"关胜","大刀"));
        list.insert(2,new Heroode(4,"林冲之后","豹子头林冲之后"));
        list.remove(2);
        //遍历
        println();
        println("正序：");
        list.show();
        //输出有效节点个数
        println("有效节点个数：" + list.getum());
        //倒数第个节点
        list.getK();

        //反转
        println();
        println("倒序：");
        list.invertedList();
        list.show();
    }
}
//定义一个单链表，来管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点，头节点不要动
    private final Heroode head = new Heroode(0,"","");

    //添加节点思路：首先到链表的最后一个节点，然后将此节点的nextId指向新节点
    public void add(Heroode heroode){
        Heroode temp = head;
        while ( != null) {
            //拿到下一个节点
            temp = ;
        }
        //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
         = heroode;
        println( +  + "添加成功！");
    }

    //指定一个节点的id，在其后面添加一个节点
    public void insert(int id, Heroode heroode){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        //跳出循环之后，就代表到了给定的id
        Heroode t = ;
         = heroode;
         = t;
        println( +  + "添加成功！");
    }

    //删除指定id的节点之后的那个节点
    //为什么不删除指定id的节点？因为单向链表只知道后面是谁，不知道前面是谁，也可以删除，
    // 但是需要再进行一次遍历，这里演示的是如何删除一个节点，所以不做过多纠结！
    public void remove(int id){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        println("移除了" + .nickname + .name);
        //这个时候，temp是要被删除的节点前面的那个节点
         = .next;
    }

    //遍历输出
    public void show(){
        Heroode temp = head;
        while ( != null){
            println( + );
            temp = ;
        }
        //上面走到最后一个节点的时候跑了，这里接着输出一下才行
        println( + );
    }

    //获取有效节点的个数
    public int getum(){
        int count = 0;
        Heroode temp = head;
        while ( != null){
            temp = ;
            count++;
        }
        return count;
    }

    //获取倒数第k个节点
    public void getK(int k){
        int count = 0;
        int index = getum() - k + 1;
        Heroode temp = head;
        while (count != index){
            temp = ;
            count++;
        }
        //此时的temp就是要的节点
        println("倒数第" + k + "个节点为：" +  + );
    }

    //单链表的反转
    public void  invertedList(){
        //如果为空或者元素数量为1，就直接返回
        if(==null || .next==null){
            return;
        }
        //初始化一个新的头节点，头节点不要动
        Heroode newHead = new Heroode(0,"","");
        Heroode next;//用来存储下一个节点，防止断链
        //当前节点
        Heroode thisode = ;//我们先拿到第一个节点
        //上一个节点，默认为空，正好将第一个元素的下一个节点设置为空，编程单链表的队尾
        Heroode last = null;
        while (thisode != null){//如果当前节点不为空，就进行下列操作
            //将当前节点之后的节点存储下来
            next = ;
            //将当前节点指向上一个与头节点连接的节点
             = last;
            //头节点指向当前节点
             = thisode;
            //将上一个节点存下来，以备后面的连接进行连接
            last = thisode;
            //将当前节点后移一个节点
            thisode = next;
        }
        //这个时候便利了所有节点，newHead这个新的头节点后面连接的元素是原链表的反转，
        // 我们将newHead的next赋值给原链表头节点的next，即可完成最终的反转
         = ;//之所以没有使得head=newHead是因为头节点不能动，要固定
    }
}

//英雄
class Heroode{
    final int id;
    final String name;
    final String nickname;
    Heroode next;

    public Heroode(int id, String name, String nickname) {
        this.id = id;
         = name;
         = nickname;
    }
}

运行结果：

4、从尾到头打印单链表（百度）

方式自选：

1、反向遍历；2、Stack栈；

思路分析：

方式一（反转遍历打印）：上面腾讯的链表反转了，再进行遍历打印即可，这种方式是不建议的，因为人家只是要求遍历打印，反转的话把链表的结构也给破坏了；

方式二：利用栈这个数据结构，将各个节点压入到栈中，利用栈先进后出的特点，实现逆序打印的效果；

栈的使用演示：

代码：

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

import java.util.Stack;

//演示栈的使用
public class TestStack {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        //入栈
        stack.add("大哥");
        stack.add("二哥");
        stack.add("三哥");
        stack.add("四哥");
        //出栈
        while (stack.size()>0){
            println(stack.pop());//pop就是从栈顶的元素取出
        }
    }
}

运行结果（for循环遍历的话是正序的）：

代码演示：

（在之前的基础上）

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

import java.util.Stack;

//测试单向链表
public class TestLinkedList {
    public static void main(String[] args) {
        //测试单链表
        SingleLinkedList list = new SingleLinkedList();
        //添加
        list.add(new Heroode(1,"宋江","及时雨"));
        list.add(new Heroode(2,"林冲","豹子头"));
        list.add(new Heroode(,"卢俊义","玉麒麟"));
        //再添加几个节点
        list.add(new Heroode(5,"吴用","智多星"));
        list.add(new Heroode(6,"公孙胜","入云龙"));
        list.add(new Heroode(7,"关胜","大刀"));
        list.insert(2,new Heroode(4,"林冲之后","豹子头林冲之后"));
        list.remove(2);
        //遍历
        println();
        println("正序：");
        list.show();
        //输出有效节点个数
        println("有效节点个数：" + list.getum());
        //倒数第个节点
        list.getK();

        //反转
//        println();
//        println("倒序：");
//        list.invertedList();
//        list.show();
        //逆序遍历
        //方式二：利用栈这个数据结构，将各个节点压入到栈中，利用栈先进后出的特点，实现逆序打印的效果；
        println("逆序遍历：");
        list.reversePrint();
    }
}
//定义一个单链表，来管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点，头节点不要动
    private final Heroode head = new Heroode(0,"","");

    //添加节点思路：首先到链表的最后一个节点，然后将此节点的nextId指向新节点
    public void add(Heroode heroode){
        Heroode temp = head;
        while ( != null) {
            //拿到下一个节点
            temp = ;
        }
        //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
         = heroode;
        println( +  + "添加成功！");
    }

    //指定一个节点的id，在其后面添加一个节点
    public void insert(int id, Heroode heroode){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        //跳出循环之后，就代表到了给定的id
        Heroode t = ;
         = heroode;
         = t;
        println( +  + "添加成功！");
    }

    //删除指定id的节点之后的那个节点
    //为什么不删除指定id的节点？因为单向链表只知道后面是谁，不知道前面是谁，也可以删除，
    // 但是需要再进行一次遍历，这里演示的是如何删除一个节点，所以不做过多纠结！
    public void remove(int id){
        Heroode temp = head;
        while (temp.id != id) {
            //拿到下一个节点
            temp = ;
        }
        println("移除了" + .nickname + .name);
        //这个时候，temp是要被删除的节点前面的那个节点
         = .next;
    }

    //遍历输出
    public void show(){
        Heroode temp = head;
        while ( != null){
            println( + );
            temp = ;
        }
        //上面走到最后一个节点的时候跑了，这里接着输出一下才行
        println( + );
    }

    //逆序打印
    public void reversePrint(){
        if(==null){
            return;
        }
        //创建一个栈，存储数据为Heroode，将英雄遍历压入栈
        Stack<Heroode> stack = new Stack<>();
        //入栈
        Heroode temp = head;
        while ( != null){
            stack.add();
            temp = ;
        }
        //出栈
        while (stack.size()>0){
            Heroode pop = stack.pop();
            println( + );
        }
    }

    //获取有效节点的个数
    public int getum(){
        int count = 0;
        Heroode temp = head;
        while ( != null){
            temp = ;
            count++;
        }
        return count;
    }

    //获取倒数第k个节点
    public void getK(int k){
        int count = 0;
        int index = getum() - k + 1;
        Heroode temp = head;
        while (count != index){
            temp = ;
            count++;
        }
        //此时的temp就是要的节点
        println("倒数第" + k + "个节点为：" +  + );
    }

    //单链表的反转
    public void  invertedList(){
        //如果为空或者元素数量为1，就直接返回
        if(==null || .next==null){
            return;
        }
        //初始化一个新的头节点，头节点不要动
        Heroode newHead = new Heroode(0,"","");
        Heroode next;//用来存储下一个节点，防止断链
        //当前节点
        Heroode thisode = ;//我们先拿到第一个节点
        //上一个节点，默认为空，正好将第一个元素的下一个节点设置为空，编程单链表的队尾
        Heroode last = null;
        while (thisode != null){//如果当前节点不为空，就进行下列操作
            //将当前节点之后的节点存储下来
            next = ;
            //将当前节点指向上一个与头节点连接的节点
             = last;
            //头节点指向当前节点
             = thisode;
            //将上一个节点存下来，以备后面的连接进行连接
            last = thisode;
            //将当前节点后移一个节点
            thisode = next;
        }
        //这个时候便利了所有节点，newHead这个新的头节点后面连接的元素是原链表的反转，
        // 我们将newHead的next赋值给原链表头节点的next，即可完成最终的反转
         = ;//之所以没有使得head=newHead是因为头节点不能动，要固定
    }
}

//英雄
class Heroode{
    final int id;
    final String name;
    final String nickname;
    Heroode next;

    public Heroode(int id, String name, String nickname) {
        this.id = id;
         = name;
         = nickname;
    }
}

运行结果：

5、合并两个有序的单链表，合并之后的链表依然有序（课后练习题）

说明：

比如第一个链表内部节点的id为1、、5、7，第二个链表内部节点的id为2，4，6，8，10，我们将这两个链表合并，要求顺序是1、2、、4、5、6、7、8、10；

思路分析：

创建一个新的链表，循环遍历两个链表的所有节点，从小到大add到新链表里面（注意add的时候不要把整个剩余链表都add进去，要进行阉割，放大就是new一个节点，使用即将被add的节点各个属性值进行初始化），谁被add了就往后移一位，直到链表末尾，如果剩下的另一个链表还有节点，直接add剩下的链表所有元素（因为原来的链表就是有序的）；

代码演示：

代码语言：javascript代码运行次数：0运行复制

package com.zb.ds;

//测试单向链表
public class TestLinkedList {
    public static void main(String[] args) {
        //测试单链表
        SingleLinkedList list = new SingleLinkedList();
        Heroode head = list.getHead();
        list.add(new Heroode(1,"宋江","及时雨"),head);
        list.add(new Heroode(,"林冲","豹子头"),head);
        list.add(new Heroode(5,"卢俊义","玉麒麟"),head);
        list.add(new Heroode(7,"吴用","智多星"),head);
        SingleLinkedList list1 = new SingleLinkedList();
        Heroode head1 = list1.getHead();
        list1.add(new Heroode(2,"大哥","大哥"),head1);
        list1.add(new Heroode(4,"二哥","二哥"),head1);
        list1.add(new Heroode(6,"三哥","三哥"),head1);
        list1.add(new Heroode(8,"四哥","四哥"),head1);
        list1.add(new Heroode(10,"五弟","五弟"),head1);
        //遍历
        println("合并之前：");
        list.show();
        list1.show();
        println("合并之后：");
        (list.getHead(),list1.getHead()).show();
    }
}
//定义一个单链表，来管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点，头节点不要动
    private final Heroode head = new Heroode(0,"","");

    //添加节点思路：首先到链表的最后一个节点，然后将此节点的nextId指向新节点
    public void add(Heroode heroode,Heroode head){
        Heroode temp = head;
        while ( != null) {
            //拿到下一个节点
            temp = ;
        }
        //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
         = heroode;
        println( +  + "添加成功！");
    }

    //遍历输出
    public void show(){
        Heroode temp = head;
        while ( != null){
            println(temp.id +  + );
            temp = ;
        }
        //上面走到最后一个节点的时候跑了，这里接着输出一下才行
        println(temp.id +  + );
    }

    //获取head
    public Heroode getHead(){
        return head;
    }

    //合并两个有序的单链表，合并之后的链表依然有序
   public static SingleLinkedList merge(Heroode head1,Heroode head2){
       SingleLinkedList list = new SingleLinkedList();
       //分别存储两个链表剩下的节点
       Heroode next1 = ;
       Heroode next2 = ;
       //循环遍历两个链表中的所有节点
       while (next1!=null || next2!=null){
           //如果两个都没循环结束
           if(next1!=null && next2!=null){
               //拿到两个列表剩余首节点的id
               int id1 = next1.id;
               int id2 = next2.id;
               if(id1<id2){
                   //注意添加的时候，不要把后面一连串都添加进来，要进行阉割之后再添加
                   list.add(new Heroode(next1.id,,),list.getHead());
                   //当添加1的时候，1需要往后走一步，2没用不需要往后走
                   next1 = ;
               }else {
                   list.add(new Heroode(next2.id,,),list.getHead());
                   //当添加2的时候，2需要往后走一步，1没用不需要往后走
                   next2 = ;
               }
           }
           //当2为空的时候，全部按顺序添加1
           if(next1!=null && next2==null){
               //这个时候就不需要阉割了
               list.add(next1,list.getHead());
               next1 = null;
           }
           //当1位空的时候，全部按顺序添加2
           if(next1==null && next2!=null){
               list.add(next2,list.getHead());
               next2 = null;
           }
       }
       return list;
   }
}

//英雄
class Heroode{
    final int id;
    final String name;
    final String nickname;
    Heroode next;

    public Heroode(int id, String name, String nickname) {
        this.id = id;
         = name;
         = nickname;
    }
}

运行结果：

（里面的0进行简单的优化处理即可！）

代码语言：javascript代码运行次数：0运行复制

及时雨宋江添加成功！
豹子头林冲添加成功！
玉麒麟卢俊义添加成功！
智多星吴用添加成功！
大哥大哥添加成功！
二哥二哥添加成功！
三哥三哥添加成功！
四哥四哥添加成功！
五弟五弟添加成功！
合并之前：
0
1及时雨宋江
豹子头林冲
5玉麒麟卢俊义
7智多星吴用
0
2大哥大哥
4二哥二哥
6三哥三哥
8四哥四哥
10五弟五弟
合并之后：
及时雨宋江添加成功！
大哥大哥添加成功！
豹子头林冲添加成功！
二哥二哥添加成功！
玉麒麟卢俊义添加成功！
三哥三哥添加成功！
智多星吴用添加成功！
四哥四哥添加成功！
0
1及时雨宋江
2大哥大哥
豹子头林冲
4二哥二哥
5玉麒麟卢俊义
6三哥三哥
7智多星吴用
8四哥四哥
10五弟五弟

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。原始发表：2025-01-06，如有侵权请联系 cloudcommunity@tencent 删除数据结构遍历链表算法java

#感谢您对电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格的认可，转载请说明来源于"电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格

本文地址：http://www.dnpztj.cn/biancheng/1197977.html

本站网友黄手帕主题曲	1秒前发表
直接add剩下的链表所有元素（因为原来的链表就是有序的）；代码演示：代码语言：javascript代码运行次数：0运行复制package com.zb.ds; //测试单向链表 public class TestLinkedList { public static void main(String[] args) { //测试单链表 SingleLinkedList list = new SingleLinkedList(); Heroode head = list.getHead(); list.add(new Heroode(1
本站网友浙传	28分钟前发表
所以不做过多纠结！ public void remove(int id){ Heroode temp = head; while (temp.id != id) { //拿到下一个节点 temp = ; } println("移除了" + .nickname + .name); //这个时候
本站网友阳性食物	20分钟前发表
与上面的代码区别不大
本站网友迎香穴	19分钟前发表
直到nextId为null

【Java数据结构和算法】004