【Java数据结构和算法】004-链表：单向链表

訾博ZiBo

发布于 2025-01-06 16:33:58

7700

代码可运行

文章被收录于专栏：全栈开发工程师全栈开发工程师

运行总次数：0

代码可运行

0、警醒自己

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

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

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

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

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

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

一、链表(Linked List)介绍

1、概述

链表是有序的列表；

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

3、上图小结

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

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

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

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

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

二、单链表的应用实例

1、单链表类属性内容

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

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

举例：

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

2、添加元素

图解：

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

说明：

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

3、遍历

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

4、代码演示

（链表 = 无限套娃！）

package com.zb.ds;

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

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

5、运行结果

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

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

6、插入节点

图解：

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

分析：

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

7、删除节点

图解：

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

分析：

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

8、代码演示

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

package com.zb.ds;

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

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

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

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

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

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

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

9、运行结果

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

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

10、关于代码演示的说明

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

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

三、单链表面试题

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

思路：

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

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

代码演示：

（在上面的基础上）

package com.zb.ds;

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

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

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

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

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

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

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

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

运行结果：

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

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

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

个人评述：

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

代码演示：

（在上面代码的基础上）

package com.zb.ds;

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

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

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

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

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

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

    //获取倒数第k个节点
    public void getK(int k){
        int count = 0;
        int index = getNum() - k + 1;
        HeroNode temp = head;
        while (count != index){
            temp = temp.next;
            count++;
        }
        //此时的temp就是要找的节点
        System.out.println("倒数第" + k + "个节点为：" + temp.nickname + temp.name);
    }
}

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

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

运行结果：

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

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

3、单链表的反转（腾讯）

说明：

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

日志：

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

代码演示：

（在之前的基础上）

package com.zb.ds;

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

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

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

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

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

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

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

    //获取倒数第k个节点
    public void getK(int k){
        int count = 0;
        int index = getNum() - k + 1;
        HeroNode temp = head;
        while (count != index){
            temp = temp.next;
            count++;
        }
        //此时的temp就是要找的节点
        System.out.println("倒数第" + k + "个节点为：" + temp.nickname + temp.name);
    }

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

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

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

运行结果：

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

方式自选：

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

思路分析：

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

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

栈的使用演示：

代码：

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){
            System.out.println(stack.pop());//pop就是从栈顶的元素取出
        }
    }
}

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

代码演示：

（在之前的基础上）

package com.zb.ds;

import java.util.Stack;

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

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

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

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

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

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

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

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

    //获取倒数第k个节点
    public void getK(int k){
        int count = 0;
        int index = getNum() - k + 1;
        HeroNode temp = head;
        while (count != index){
            temp = temp.next;
            count++;
        }
        //此时的temp就是要找的节点
        System.out.println("倒数第" + k + "个节点为：" + temp.nickname + temp.name);
    }

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

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

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

运行结果：

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

说明：

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

思路分析：

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

代码演示：

package com.zb.ds;

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

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

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

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

    //合并两个有序的单链表，合并之后的链表依然有序
   public static SingleLinkedList merge(HeroNode head1,HeroNode head2){
       SingleLinkedList list = new SingleLinkedList();
       //分别存储两个链表剩下的节点
       HeroNode next1 = head1.next;
       HeroNode next2 = head2.next;
       //循环遍历两个链表中的所有节点
       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 HeroNode(next1.id,next1.name,next1.nickname),list.getHead());
                   //当添加1的时候，1需要往后走一步，2没用不需要往后走
                   next1 = next1.next;
               }else {
                   list.add(new HeroNode(next2.id,next2.name,next2.nickname),list.getHead());
                   //当添加2的时候，2需要往后走一步，1没用不需要往后走
                   next2 = next2.next;
               }
           }
           //当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 HeroNode{
    final int id;
    final String name;
    final String nickname;
    HeroNode next;

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

运行结果：

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-06，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度