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

心已赠人 2023-10-05 12:58 17阅读 0赞

# **目录** #

0、警醒自己

一、链表(Linked List)介绍

1、概述

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

3、上图小结

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

二、单链表的应用实例

1、单链表类属性内容

举例：

2、添加元素

图解：

说明：

3、遍历

4、代码演示

5、运行结果

6、插入节点

图解：

分析：

7、删除节点

图解：

分析：

8、代码演示

9、运行结果

10、关于代码演示的说明

三、单链表面试题

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

思路：

代码演示：

运行结果：

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

个人评述：

代码演示：

运行结果：

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

说明：

日志：

代码演示：

运行结果：

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

方式自选：

思路分析：

栈的使用演示：

代码演示：

运行结果：

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

说明：

思路分析：

代码演示：

运行结果：

--------------------

# 0、警醒自己 #

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

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

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

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

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

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

# 一、链表(Linked List)介绍 #

## 1、概述 ##

链表是有序的列表；

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70][]

## 3、上图小结 ##

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

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

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1][]

# 二、单链表的应用实例 #

## 1、单链表类属性内容 ##

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

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

### 举例： ###

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

## 2、添加元素 ##

### 图解： ###

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2][]

### 说明： ###

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

## 3、遍历 ##

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

## 4、代码演示 ##

（链表 = 无限套娃！）

## 5、运行结果 ##

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

## 6、插入节点 ##

### 图解： ###

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3][]

### 分析： ###

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

## 7、删除节点 ##

### 图解： ###

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 4][]

### 分析： ###

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

## 8、代码演示 ##

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

## 9、运行结果 ##

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

## 10、关于代码演示的说明 ##

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

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

# 三、单链表面试题 #

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

### 思路： ###

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

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

### 代码演示： ###

（在上面的基础上）

### 运行结果： ###

及时雨宋江添加成功！
    豹子头林冲添加成功！
    玉麒麟卢俊义添加成功！
    豹子头林冲之后林冲之后添加成功！
    移除了豹子头林冲之后林冲之后
    
    及时雨宋江
    豹子头林冲
    玉麒麟卢俊义
    有效节点个数：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;
        }
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 5][]

## 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循环遍历的话是正序的）：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 6][]

### 代码演示： ###

（在之前的基础上）

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;
        }
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 7][]

## 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五弟五弟

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201031104357757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201031105459403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201031111258856.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201031133300446.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201031133628410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201102083827648.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201102085431208.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201102090243109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70