单链表介绍和内存布局

链表(Linked List)是有序的列表，但他在内存中的存储如下图：

image-20220910184333237

结论：

  • 链表是以节点的方式来存储，是链式存储；
  • 每个节点包含data域，next域(来指向下一个节点)；
  • 根据图发现，链表的各个节点不一定是连续存放；
  • 链表分带头节点的链表和没带头的链表；

单链表(带头节点)逻辑结构示意图：

image-20220910194229884

单链表创建和遍历的分析实现

单链表的应用实例

使用带head头的单项链表实现-水浒传英雄排行榜的管理，要求：

  • 完成对英雄任务的CRUD操作；
  • 第一种方法在添加英雄时，直接添加到链表尾部；
  • 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果该排名存在，则添加失败并提示)；

单链表代码实现分析

image-20220910201442834

添加(创建)：

  1. 先创建一个head头节点，作用就是表示单链表的头；
  2. 后面我们每添加一个节点，就直接加入到链表的最后遍历；
  3. 通过一个辅助变量，帮助遍历整个链表；

代码实现

第一种方法实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package com.jokerdig.linkedlist;

/**
 * @author Joker大雄
 * @data 2022/9/10 - 20:16
 **/
public class SIngleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"武松","行者");
        HeroNode hero5 = new HeroNode(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 加入链表
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        singleLinkedList.add(hero5);
        // 显示链表
        singleLinkedList.list();
    }
}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode head = new HeroNode(0,"","");

    // 添加节点到单向链表
    /*
        思路，当不考虑编号顺序时
        1. 找到当前链表的最后节点
        2. 将最后这个几点的next 执行新的节点
     */
    public void add(HeroNode heroNode){
        // head不能动，因此我们呢需要复制变量temp
        HeroNode temp = head;
        // 遍历链表，找到最后
        while(true){
            // 当next为null，说明到最后了
            if(temp.next==null){
                break;
            }
            // 如果没有找到,就将temp后移
            temp = temp.next;
        }
        // 当结束while循环时，temp指向链表最后
        temp.next = heroNode;
    }

    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一个节点

    // 构造器
    public HeroNode(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
HeroNode{no=1, name='宋江', nickname='及时雨}
HeroNode{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode{no=3, name='吴用', nickname='智多星}
HeroNode{no=4, name='武松', nickname='行者}
HeroNode{no=5, name='林冲', nickname='豹子头}

Process finished with exit code 0

单链表按顺序插入节点

思路分析

image-20220910204950910

需要按照编号的顺序添加：

  • 首先找到新添加的节点位置，通过辅助变量(指针)，使用遍历来定位；
  • 新的节点next = temp.next
  • 将temp.next = 新节点

代码实现

第二种方法实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package com.jokerdig.linkedlist;

/**
 * @author Joker大雄
 * @data 2022/9/10 - 20:16
 **/
public class SIngleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"武松","行者");
        HeroNode hero5 = new HeroNode(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 加入链表，按照编号顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3);
        // 显示链表
        singleLinkedList.list();


    }
}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode head = new HeroNode(0,"","");

    // 添加节点到单向链表
    /*
        思路，当不考虑编号顺序时
        1. 找到当前链表的最后节点
        2. 将最后这个几点的next 执行新的节点
     */
    public void add(HeroNode heroNode){
        // head不能动，因此我们呢需要复制变量temp
        HeroNode temp = head;
        // 遍历链表，找到最后
        while(true){
            // 当next为null，说明到最后了
            if(temp.next==null){
                break;
            }
            // 如果没有找到,就将temp后移
            temp = temp.next;
        }
        // 当结束while循环时，temp指向链表最后
        temp.next = heroNode;
    }

    /*
        第二种方法，按照顺序添加
     */
    public void addByOrder(HeroNode heroNode){
        // 辅助变量
        HeroNode temp = head;
        // 因为是单链表，所有我们找的时位于添加位置的前一个节点
        boolean flag = false; // 添加的编号是否存在，默认为false
        while(true){
            if(temp.next == null){
                // temp已经在链表的最后
                break;
            }
            if(temp.next.no>heroNode.no){
                // 说明添加位置就在temp的后面
                break;
            }else if(temp.next.no == heroNode.no){
                // 说明这个位置已经有hero存在了，不能再添加
                flag = true;
                break;
            }
            temp = temp.next; // 后移
        }
        // 判断flag的值
        if(flag){
            // 不能添加，编号已经存在
            System.out.println("该英雄编号"+heroNode.no+"已经存在");
        }else{
            // 可以添加到链表中，再temp后
            heroNode.next = temp.next;
            temp.next = heroNode;

        }

    }

    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一个节点

    // 构造器
    public HeroNode(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
8
该英雄编号3已经存在
HeroNode{no=1, name='宋江', nickname='及时雨}
HeroNode{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode{no=3, name='吴用', nickname='智多星}
HeroNode{no=4, name='武松', nickname='行者}
HeroNode{no=5, name='林冲', nickname='豹子头}

Process finished with exit code 0

单链表节点的修改

修改代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
package com.jokerdig.linkedlist;

/**
 * @author Joker大雄
 * @data 2022/9/10 - 20:16
 **/
public class SIngleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"武松","行者");
        HeroNode hero5 = new HeroNode(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 加入链表，按照编号顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3);
        // 显示链表
        singleLinkedList.list();
        // 测试修改
        singleLinkedList.update(new HeroNode(1,"不是松江","不是及时雨"));
        singleLinkedList.update(new HeroNode(7,"巴拉巴拉","巴拉巴拉"));
        // 查看修改后的链表
        System.out.println("============修改后的链表=============");
        singleLinkedList.list();
    }
}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode head = new HeroNode(0,"","");

    // 添加节点到单向链表
    /*
        思路，当不考虑编号顺序时
        1. 找到当前链表的最后节点
        2. 将最后这个几点的next 执行新的节点
     */
    public void add(HeroNode heroNode){
        // head不能动，因此我们呢需要复制变量temp
        HeroNode temp = head;
        // 遍历链表，找到最后
        while(true){
            // 当next为null，说明到最后了
            if(temp.next==null){
                break;
            }
            // 如果没有找到,就将temp后移
            temp = temp.next;
        }
        // 当结束while循环时，temp指向链表最后
        temp.next = heroNode;
    }

    /*
        第二种方法，按照顺序添加
     */
    public void addByOrder(HeroNode heroNode){
        // 辅助变量
        HeroNode temp = head;
        // 因为是单链表，所有我们找的时位于添加位置的前一个节点
        boolean flag = false; // 添加的编号是否存在，默认为false
        while(true){
            if(temp.next == null){
                // temp已经在链表的最后
                break;
            }
            if(temp.next.no>heroNode.no){
                // 说明添加位置就在temp的后面
                break;
            }else if(temp.next.no == heroNode.no){
                // 说明这个位置已经有hero存在了，不能再添加
                flag = true;
                break;
            }
            temp = temp.next; // 后移
        }
        // 判断flag的值
        if(flag){
            // 不能添加，编号已经存在
            System.out.println("该英雄编号"+heroNode.no+"已经存在");
        }else{
            // 可以添加到链表中，再temp后
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 修改链表信息,根据编号来修改
    public void update(HeroNode newHeroNode){
        // 判断是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 找到需要修改的节点，根据no编号
        // 定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false; // 表示是否找到该节点
        while(true){
            if(temp == null){
                break; // 到链表遍历完毕
            }
            if(temp.no == newHeroNode.no){
                // 找到要修改的节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag判断是否找到了要修改的节点
        if(flag){
            // 进行修改
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else{
            // 没有找到该节点
            System.out.println("编号为："+newHeroNode.no+"的英雄未在链表中找到");
        }
    }

    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一个节点

    // 构造器
    public HeroNode(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
该英雄编号3已经存在
HeroNode{no=1, name='宋江', nickname='及时雨}
HeroNode{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode{no=3, name='吴用', nickname='智多星}
HeroNode{no=4, name='武松', nickname='行者}
HeroNode{no=5, name='林冲', nickname='豹子头}
编号为：7的英雄未在链表中找到
============修改后的链表=============
HeroNode{no=1, name='不是松江', nickname='不是及时雨}
HeroNode{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode{no=3, name='吴用', nickname='智多星}
HeroNode{no=4, name='武松', nickname='行者}
HeroNode{no=5, name='林冲', nickname='豹子头}

Process finished with exit code 0

单链表节点的删除

思路分析

image-20220912103632727

从单链表删除一个节点：

  1. 创建辅助变量temp，先找到需要删除节点的前一个节点；
  2. temp.next = temp.next.next;
  3. 而要删除的那个节点(没有引用指向)，就会被Java的GC垃圾回收机制回收掉；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
package com.jokerdig.linkedlist;

/**
 * @author Joker大雄
 * @data 2022/9/10 - 20:16
 **/
public class SIngleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"武松","行者");
        HeroNode hero5 = new HeroNode(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 加入链表，按照编号顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3);
        // 显示链表
        singleLinkedList.list();
        // 测试修改
        singleLinkedList.update(new HeroNode(1,"不是松江","不是及时雨"));
        singleLinkedList.update(new HeroNode(7,"巴拉巴拉","巴拉巴拉"));
        // 查看修改后的链表
        System.out.println("============修改后的链表=============");
        singleLinkedList.list();

        // 测试删除
        singleLinkedList.delete(5);
        // 测试删除不存在编号
        singleLinkedList.delete(6);
        // 查看删除后的链表
        System.out.println("============删除后的链表=============");
        singleLinkedList.list();
    }
}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode head = new HeroNode(0,"","");

    // 添加节点到单向链表
    /*
        思路，当不考虑编号顺序时
        1. 找到当前链表的最后节点
        2. 将最后这个几点的next 执行新的节点
     */
    public void add(HeroNode heroNode){
        // head不能动，因此我们呢需要复制变量temp
        HeroNode temp = head;
        // 遍历链表，找到最后
        while(true){
            // 当next为null，说明到最后了
            if(temp.next==null){
                break;
            }
            // 如果没有找到,就将temp后移
            temp = temp.next;
        }
        // 当结束while循环时，temp指向链表最后
        temp.next = heroNode;
    }

    /*
        第二种方法，按照顺序添加
     */
    public void addByOrder(HeroNode heroNode){
        // 辅助变量
        HeroNode temp = head;
        // 因为是单链表，所有我们找的时位于添加位置的前一个节点
        boolean flag = false; // 添加的编号是否存在，默认为false
        while(true){
            if(temp.next == null){
                // temp已经在链表的最后
                break;
            }
            if(temp.next.no>heroNode.no){
                // 说明添加位置就在temp的后面
                break;
            }else if(temp.next.no == heroNode.no){
                // 说明这个位置已经有hero存在了，不能再添加
                flag = true;
                break;
            }
            temp = temp.next; // 后移
        }
        // 判断flag的值
        if(flag){
            // 不能添加，编号已经存在
            System.out.println("该英雄编号"+heroNode.no+"已经存在");
        }else{
            // 可以添加到链表中，再temp后
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 修改链表信息,根据编号来修改
    public void update(HeroNode newHeroNode){
        // 判断是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 找到需要修改的节点，根据no编号
        // 定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false; // 表示是否找到该节点
        while(true){
            if(temp == null){
                break; // 到链表遍历完毕
            }
            if(temp.no == newHeroNode.no){
                // 找到要修改的节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag判断是否找到了要修改的节点
        if(flag){
            // 进行修改
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else{
            // 没有找到该节点
            System.out.println("编号为："+newHeroNode.no+"的英雄未在链表中找到");
        }
    }

    // 删除链表信息
    // temp辅助知道到删除节点的前一个
    // 比较的时候，是temp.next.no 和删除节点的no进行比较
    public void delete(int deleteNo){
        HeroNode temp = head;
        boolean flag = false;//是否找到
        while(true){
            if(temp.next == null){
                // 到链表末尾
                break;
            }
            if(temp.next.no == deleteNo){
                // 找到了待删除的节点的temp
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            // 找到了
            temp.next = temp.next.next;
        }else{
            System.out.println("要删除的节点"+deleteNo+"不存在");
        }
    }


    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一个节点

    // 构造器
    public HeroNode(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
HeroNode{no=1, name='不是松江', nickname='不是及时雨}
HeroNode{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode{no=3, name='吴用', nickname='智多星}
HeroNode{no=4, name='武松', nickname='行者}
HeroNode{no=5, name='林冲', nickname='豹子头}
要删除的节点6不存在
============删除后的链表=============
HeroNode{no=1, name='不是松江', nickname='不是及时雨}
HeroNode{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode{no=3, name='吴用', nickname='智多星}
HeroNode{no=4, name='武松', nickname='行者}

Process finished with exit code 0

单链表面试题

单链表常见面试题：

  1. 求单链表中有效节点的个数；
  2. 查找单链表中的倒数第k个节点；
  3. 单链表的反转；
  4. 从尾到头打印单链表(方式1：反向遍历，方式2：Stack栈)；

第一题

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package com.jokerdig.linkedlist;

/**
 * @author Joker大雄
 * @data 2022/9/12 - 10:58
 **/
public class SingleLinkedListTest1 {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode1 hero1 = new HeroNode1(1,"宋江","及时雨");
        HeroNode1 hero2 = new HeroNode1(2,"卢俊义","玉麒麟");
        HeroNode1 hero3 = new HeroNode1(3,"吴用","智多星");
        HeroNode1 hero4 = new HeroNode1(4,"武松","行者");
        HeroNode1 hero5 = new HeroNode1(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList1 singleLinkedList = new SingleLinkedList1();
        // 加入链表，按照编号顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        // 显示链表
        singleLinkedList.list();
        // 调用遍历方法
        System.out.println("有"+getLength(singleLinkedList.getHead())+"个有效节点");
    }
    // 求单链表中有效节点的个数(如果带头节点需要不统计)

    /**
     *
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode1 head){
        if(head.next == null){
            // 这是空列表
            return 0;
        }
        int length = 0;
        // 定义一个辅助的变量
        HeroNode1 cur = head.next;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList1{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode1 head = new HeroNode1(0,"","");
    // 返回头节点
    public HeroNode1 getHead() {
        return head;
    }

    /*
            第二种方法，按照顺序添加
         */
    public void addByOrder(HeroNode1 heroNode){
        // 辅助变量
        HeroNode1 temp = head;
        // 因为是单链表，所有我们找的时位于添加位置的前一个节点
        boolean flag = false; // 添加的编号是否存在，默认为false
        while(true){
            if(temp.next == null){
                // temp已经在链表的最后
                break;
            }
            if(temp.next.no>heroNode.no){
                // 说明添加位置就在temp的后面
                break;
            }else if(temp.next.no == heroNode.no){
                // 说明这个位置已经有hero存在了，不能再添加
                flag = true;
                break;
            }
            temp = temp.next; // 后移
        }
        // 判断flag的值
        if(flag){
            // 不能添加，编号已经存在
            System.out.println("该英雄编号"+heroNode.no+"已经存在");
        }else{
            // 可以添加到链表中，再temp后
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode1 temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode1{
    public int no;
    public String name;
    public String nickname;
    public HeroNode1 next; // 指向下一个节点

    // 构造器
    public HeroNode1(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode1{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
8
HeroNode1{no=1, name='宋江', nickname='及时雨}
HeroNode1{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode1{no=3, name='吴用', nickname='智多星}
HeroNode1{no=4, name='武松', nickname='行者}
HeroNode1{no=5, name='林冲', nickname='豹子头}
有5个有效节点

Process finished with exit code 0

第二题

思路分析：

  1. 编写一个方法，接收head节点，同时接收一个index(表示倒数第index个节点)；
  2. 先把链表从头到尾遍历，得到链表的总长度getLength；
  3. 得到size，从链表第一个开始遍历到(seiz-index)个；
  4. 如果找到就返回该节点，否则返回null；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
package com.jokerdig.linkedlist;

/**
 * @author Joker大雄
 * @data 2022/9/12 - 10:58
 **/
public class SingleLinkedListTest1 {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode1 hero1 = new HeroNode1(1,"宋江","及时雨");
        HeroNode1 hero2 = new HeroNode1(2,"卢俊义","玉麒麟");
        HeroNode1 hero3 = new HeroNode1(3,"吴用","智多星");
        HeroNode1 hero4 = new HeroNode1(4,"武松","行者");
        HeroNode1 hero5 = new HeroNode1(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList1 singleLinkedList = new SingleLinkedList1();
        // 加入链表，按照编号顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        // 显示链表
        singleLinkedList.list();
        // 测试第一题调用遍历方法
        // System.out.println("有"+getLength(singleLinkedList.getHead())+"个有效节点");
        // 测试第二题,找到倒数第一个
        HeroNode1 res = findLastIndexNode(singleLinkedList.getHead(),1);
        System.out.println("res="+res);

    }
    // 求单链表中有效节点的个数(如果带头节点需要不统计)
    /**
     *
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode1 head){
        if(head.next == null){
            // 这是空列表
            return 0;
        }
        int length = 0;
        // 定义一个辅助的变量
        HeroNode1 cur = head.next;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 第二题：查找查找单链表中的倒数第k个节点
    public static HeroNode1 findLastIndexNode(HeroNode1 head,int index){
        // 判断链表是否为空
        if(head.next == null){
            return null;
        }
        // 第一个遍历得到链表的长度
        int size = getLength(head);
        // 第二次遍历 size-index位置，就是倒数第K个节点
        // 先做一个index校验
        if(index <= 0|| index>size){
            return null;
        }
        // 定义一个辅助变量
        HeroNode1 cur = head.next;
        // for循环定位到index
        for (int i = 0; i < size - index; i++) {
            cur = cur.next; // 向后移动
        }
        return cur;
    }

}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList1{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode1 head = new HeroNode1(0,"","");
    // 返回头节点
    public HeroNode1 getHead() {
        return head;
    }

    /*
            第二种方法，按照顺序添加
         */
    public void addByOrder(HeroNode1 heroNode){
        // 辅助变量
        HeroNode1 temp = head;
        // 因为是单链表，所有我们找的时位于添加位置的前一个节点
        boolean flag = false; // 添加的编号是否存在，默认为false
        while(true){
            if(temp.next == null){
                // temp已经在链表的最后
                break;
            }
            if(temp.next.no>heroNode.no){
                // 说明添加位置就在temp的后面
                break;
            }else if(temp.next.no == heroNode.no){
                // 说明这个位置已经有hero存在了，不能再添加
                flag = true;
                break;
            }
            temp = temp.next; // 后移
        }
        // 判断flag的值
        if(flag){
            // 不能添加，编号已经存在
            System.out.println("该英雄编号"+heroNode.no+"已经存在");
        }else{
            // 可以添加到链表中，再temp后
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode1 temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode1{
    public int no;
    public String name;
    public String nickname;
    public HeroNode1 next; // 指向下一个节点

    // 构造器
    public HeroNode1(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode1{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
8
9
HeroNode1{no=1, name='宋江', nickname='及时雨}
HeroNode1{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode1{no=3, name='吴用', nickname='智多星}
HeroNode1{no=4, name='武松', nickname='行者}
HeroNode1{no=5, name='林冲', nickname='豹子头}
    
res=HeroNode1{no=5, name='林冲', nickname='豹子头}

Process finished with exit code 0

第三题

思路分析：

将链表的顺序反转，并非只把值替换了；

image-20220912125642191

  1. 先去定义一个节点reverseHead = new HeroNode1();
  2. 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表的最前端；
  3. 把原链表的head.next=reverseHead.next;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
package com.jokerdig.linkedlist;

/**
 * @author Joker大雄
 * @data 2022/9/12 - 10:58
 **/
public class SingleLinkedListTest1 {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode1 hero1 = new HeroNode1(1,"宋江","及时雨");
        HeroNode1 hero2 = new HeroNode1(2,"卢俊义","玉麒麟");
        HeroNode1 hero3 = new HeroNode1(3,"吴用","智多星");
        HeroNode1 hero4 = new HeroNode1(4,"武松","行者");
        HeroNode1 hero5 = new HeroNode1(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList1 singleLinkedList = new SingleLinkedList1();
        // 加入链表，按照编号顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        // 显示链表
        singleLinkedList.list();
        // 测试第一题调用遍历方法
        // System.out.println("有"+getLength(singleLinkedList.getHead())+"个有效节点");
        // 测试第二题,找到倒数第一个
        // HeroNode1 res = findLastIndexNode(singleLinkedList.getHead(),1);
        // System.out.println("res="+res);
        // 测试第三题
        reverseList(singleLinkedList.getHead());
        System.out.println("===========反转后的链表信息=========");
        singleLinkedList.list();

    }
    // 求单链表中有效节点的个数(如果带头节点需要不统计)
    /**
     *
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode1 head){
        if(head.next == null){
            // 这是空列表
            return 0;
        }
        int length = 0;
        // 定义一个辅助的变量
        HeroNode1 cur = head.next;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 第二题：查找查找单链表中的倒数第k个节点
    public static HeroNode1 findLastIndexNode(HeroNode1 head,int index){
        // 判断链表是否为空
        if(head.next == null){
            return null;
        }
        // 第一个遍历得到链表的长度
        int size = getLength(head);
        // 第二次遍历 size-index位置，就是倒数第K个节点
        // 先做一个index校验
        if(index <= 0|| index>size){
            return null;
        }
        // 定义一个辅助变量
        HeroNode1 cur = head.next;
        // for循环定位到index
        for (int i = 0; i < size - index; i++) {
            cur = cur.next; // 向后移动
        }
        return cur;
    }

    // 第三题 将单链表反转
    public static void reverseList(HeroNode1 head){
        // 如果当前链表为空，或只有一个节点，不需要反转
        if(head.next == null || head.next.next == null){
            return ;
        }
        // 定义辅助指针，帮我们遍历原来的链表
        HeroNode1 cur = head.next;
        HeroNode1 next = null; // 指向当前节点cur的下一个节点
        HeroNode1 reverseHead = new HeroNode1(0,"","");
        // 遍历原来的链表,并从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表的最前端；
        while(cur!=null){
            next = cur.next;// 暂时保存当前节点的下一个节点
            cur.next = reverseHead.next;// 将cur的下一个节点指向新链表最前端
            reverseHead.next = cur; // 将cur连接到新的链表上
            cur = next; // 让cur后移
        }
        // 将head.next指向reverseHead.next,实现了单链表的反转
        head.next = reverseHead.next;
    }

}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList1{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode1 head = new HeroNode1(0,"","");
    // 返回头节点
    public HeroNode1 getHead() {
        return head;
    }

    /*
            第二种方法，按照顺序添加
         */
    public void addByOrder(HeroNode1 heroNode){
        // 辅助变量
        HeroNode1 temp = head;
        // 因为是单链表，所有我们找的时位于添加位置的前一个节点
        boolean flag = false; // 添加的编号是否存在，默认为false
        while(true){
            if(temp.next == null){
                // temp已经在链表的最后
                break;
            }
            if(temp.next.no>heroNode.no){
                // 说明添加位置就在temp的后面
                break;
            }else if(temp.next.no == heroNode.no){
                // 说明这个位置已经有hero存在了，不能再添加
                flag = true;
                break;
            }
            temp = temp.next; // 后移
        }
        // 判断flag的值
        if(flag){
            // 不能添加，编号已经存在
            System.out.println("该英雄编号"+heroNode.no+"已经存在");
        }else{
            // 可以添加到链表中，再temp后
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode1 temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode1{
    public int no;
    public String name;
    public String nickname;
    public HeroNode1 next; // 指向下一个节点

    // 构造器
    public HeroNode1(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode1{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
HeroNode1{no=1, name='宋江', nickname='及时雨}
HeroNode1{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode1{no=3, name='吴用', nickname='智多星}
HeroNode1{no=4, name='武松', nickname='行者}
HeroNode1{no=5, name='林冲', nickname='豹子头}
===========反转后的链表信息=========
HeroNode1{no=5, name='林冲', nickname='豹子头}
HeroNode1{no=4, name='武松', nickname='行者}
HeroNode1{no=3, name='吴用', nickname='智多星}
HeroNode1{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode1{no=1, name='宋江', nickname='及时雨}

Process finished with exit code 0

第四题

思路分析：

  1. 题目要求就是逆序打印单链表
  2. 方式1：先将单链表进行反转，然后在遍历(但这样做破坏了原来单链表结构)；
  3. 方式2：利用Stack栈数据结构，将各个节点压入到栈中，利用栈的先进后出特点，就可以实现逆序打印；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
package com.jokerdig.linkedlist;

import java.util.Stack;

/**
 * @author Joker大雄
 * @data 2022/9/12 - 10:58
 **/
public class SingleLinkedListTest1 {
    public static void main(String[] args) {
        // 测试
        // 创建节点
        HeroNode1 hero1 = new HeroNode1(1,"宋江","及时雨");
        HeroNode1 hero2 = new HeroNode1(2,"卢俊义","玉麒麟");
        HeroNode1 hero3 = new HeroNode1(3,"吴用","智多星");
        HeroNode1 hero4 = new HeroNode1(4,"武松","行者");
        HeroNode1 hero5 = new HeroNode1(5,"林冲","豹子头");
        // 创建链表
        SingleLinkedList1 singleLinkedList = new SingleLinkedList1();
        // 加入链表，按照编号顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero5);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        // 显示链表
        singleLinkedList.list();
        // 测试第一题调用遍历方法
        // System.out.println("有"+getLength(singleLinkedList.getHead())+"个有效节点");
        // 测试第二题,找到倒数第一个
        // HeroNode1 res = findLastIndexNode(singleLinkedList.getHead(),1);
        // System.out.println("res="+res);
        // 测试第三题
        // reverseList(singleLinkedList.getHead());
        // System.out.println("===========反转后的链表信=========");
        // singleLinkedList.list();
        // 测试第四题
        System.out.println("===========使用栈实现逆序打印单链表=========");
        reversePrint(singleLinkedList.getHead());

    }
    // 求单链表中有效节点的个数(如果带头节点需要不统计)
    /**
     *
     * @param head 链表的头节点
     * @return 有效节点的个数
     */
    public static int getLength(HeroNode1 head){
        if(head.next == null){
            // 这是空列表
            return 0;
        }
        int length = 0;
        // 定义一个辅助的变量
        HeroNode1 cur = head.next;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 第二题：查找查找单链表中的倒数第k个节点
    public static HeroNode1 findLastIndexNode(HeroNode1 head,int index){
        // 判断链表是否为空
        if(head.next == null){
            return null;
        }
        // 第一个遍历得到链表的长度
        int size = getLength(head);
        // 第二次遍历 size-index位置，就是倒数第K个节点
        // 先做一个index校验
        if(index <= 0|| index>size){
            return null;
        }
        // 定义一个辅助变量
        HeroNode1 cur = head.next;
        // for循环定位到index
        for (int i = 0; i < size - index; i++) {
            cur = cur.next; // 向后移动
        }
        return cur;
    }

    // 第三题 将单链表反转
    public static void reverseList(HeroNode1 head){
        // 如果当前链表为空，或只有一个节点，不需要反转
        if(head.next == null || head.next.next == null){
            return ;
        }
        // 定义辅助指针，帮我们遍历原来的链表
        HeroNode1 cur = head.next;
        HeroNode1 next = null; // 指向当前节点cur的下一个节点
        HeroNode1 reverseHead = new HeroNode1(0,"","");
        // 遍历原来的链表,并从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表的最前端；
        while(cur!=null){
            next = cur.next;// 暂时保存当前节点的下一个节点
            cur.next = reverseHead.next;// 将cur的下一个节点指向新链表最前端
            reverseHead.next = cur; // 将cur连接到新的链表上
            cur = next; // 让cur后移
        }
        // 将head.next指向reverseHead.next,实现了单链表的反转
        head.next = reverseHead.next;
    }

    // 第四题：从尾到头打印单链表，使用方式2
    public static void reversePrint(HeroNode1 head){
        if(head.next == null){
            return ; // 空链表
        }
        // 创建一个栈，将链表各个节点放入栈中
        Stack<HeroNode1> stack = new Stack<HeroNode1>();
        HeroNode1 cur = head.next;
        // 将链表所有节点压入栈
        while(cur!=null){
            stack.push(cur);//节点压入栈
            cur = cur.next; // 后移
        }
        // 将栈中节点打印 pop
        while(stack.size()>0){
            System.out.println(stack.pop());// 先进后出
        }
    }


}
// 定义单链表SingleLinkedList，来管理我们的英雄
class SingleLinkedList1{
    // 初始化一个head节点，一般不要动,也不存放数据
    private HeroNode1 head = new HeroNode1(0,"","");
    // 返回头节点
    public HeroNode1 getHead() {
        return head;
    }

    /*
            第二种方法，按照顺序添加
         */
    public void addByOrder(HeroNode1 heroNode){
        // 辅助变量
        HeroNode1 temp = head;
        // 因为是单链表，所有我们找的时位于添加位置的前一个节点
        boolean flag = false; // 添加的编号是否存在，默认为false
        while(true){
            if(temp.next == null){
                // temp已经在链表的最后
                break;
            }
            if(temp.next.no>heroNode.no){
                // 说明添加位置就在temp的后面
                break;
            }else if(temp.next.no == heroNode.no){
                // 说明这个位置已经有hero存在了，不能再添加
                flag = true;
                break;
            }
            temp = temp.next; // 后移
        }
        // 判断flag的值
        if(flag){
            // 不能添加，编号已经存在
            System.out.println("该英雄编号"+heroNode.no+"已经存在");
        }else{
            // 可以添加到链表中，再temp后
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 显示链表(遍历)
    public void list(){
        // 判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 头节点不动，因此我们需要一个辅助变量来遍历
        HeroNode1 temp = head.next;
        while(true){
            // 判断是否到链表末尾
            if(temp == null){
                break;
            }
            // 输出节点的信息
            System.out.println(temp);
            // 输出信息后，需要将temp后移
            temp = temp.next;
        }
    }
}
// 创建HeroNode,每个HeroNode对象就是一个节点
class HeroNode1{
    public int no;
    public String name;
    public String nickname;
    public HeroNode1 next; // 指向下一个节点

    // 构造器
    public HeroNode1(int no,String name,String hickname){
        this.no = no;
        this.name = name;
        this.nickname = hickname;
    }

    // toString
    @Override
    public String toString() {
        return "HeroNode1{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
HeroNode1{no=1, name='宋江', nickname='及时雨}
HeroNode1{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode1{no=3, name='吴用', nickname='智多星}
HeroNode1{no=4, name='武松', nickname='行者}
HeroNode1{no=5, name='林冲', nickname='豹子头}
===========使用栈实现逆序打印单链表=========
HeroNode1{no=5, name='林冲', nickname='豹子头}
HeroNode1{no=4, name='武松', nickname='行者}
HeroNode1{no=3, name='吴用', nickname='智多星}
HeroNode1{no=2, name='卢俊义', nickname='玉麒麟}
HeroNode1{no=1, name='宋江', nickname='及时雨}

Process finished with exit code 0