【数据结构(二)】单链表（3）

摘要：在Java中，可以使用类来实现链表结构，每个节点作为类的实例，包含数据和指向下一个节点的引用（以及可能的前一个节点的引用，对于双向链表）。通过操作节点的引用，可以实现链表的各种操作，如插入、删除、查找等。

1. 链表介绍

相关概念：

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的引用。链表有多种类型，包括单向链表、双向链表和循环链表。

单向链表（Singly Linked List）：每个节点包含数据和指向下一个节点的引用。
双向链表（Doubly Linked List）：每个节点包含数据、指向前一个节点的引用和指向下一个节点的引用。
循环链表（Circular Linked List）：尾节点指向头节点，形成一个环形结构。

链表的优点之一是可以动态地分配内存空间，而数组在创建时需要确定大小。然而，链表的缺点包括不能随机访问元素，需要从头开始逐个遍历，而且需要额外的空间来存储指针。

链表是有序的列表，但是它在内存中是存储如下：

在这里插入图片描述

小结上图:

链表是以节点的方式来存储，是链式存储 ；
每个节点包含 data域， next域：指向下一个节点；
如图：发现链表的各个节点不一定是连续存储；

链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

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

在这里插入图片描述

2. 单链表应用实例

使用带 head 头的单向链表实现 –水浒英雄排行榜管理，完成对英雄人物的增、删、改、查操作。有两种方式实现，解释如下：

给链表中的数据加入编号属性，加入需要添加4个链表数据，其编号分别为1、2、3、4。
①按照添加顺序（顺序添加方式）：根据添加的顺序依次加入到链表中（如：添加顺序是1、4、2、3，在链表中的顺序也是1、4、2、3。）
②按照编号顺序（编号顺序添加方式）：对加入链表中数据进行编号，根据编号进行排序（如：添加的顺序是1、4、2、3，而在链表中会按照1、2、3、4编号顺序）

2.1. 顺序添加方式

2.1.1. 思路分析

第一种方法在添加英雄时，直接添加到链表的尾部

思路分析示意图：

在这里插入图片描述

2.1.2. 代码实现

按照加入的先后顺序形成链表

package linkedlist;

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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //加入：按照加入的先后顺序形成链表
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);

        //显示
        singleLinkedList.list();
    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }

    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
  
}
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

运行结果：

在这里插入图片描述

2.2. 按照编号顺序添加方式

2.2.1. 思路分析

第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)

思路的分析示意图：

在这里插入图片描述

按照编号的顺序添加

首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
新的节点.next = temp.next
将temp.next = 新的节点

2.2.2. 代码实现

package linkedlist;

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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //加入
        // singleLinkedList.add(hero1);
        // singleLinkedList.add(hero4);
        // singleLinkedList.add(hero2);
        // singleLinkedList.add(hero3);

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3);

        //显示
        singleLinkedList.list();
    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为单列表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        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) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前链表
        }

        //判断flag的值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号 %d 已经存在了，不能添加\n", heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }


    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
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

上述代码，添加的顺序是按照节点1、4、2、3、3的顺序添加，最后实现的结果是按照编号的顺序添加，并且如果重复添加会给出重复信息。

运行结果：

在这里插入图片描述

3. 单链表节点的修改

3.1. 思路分析

思路
(1) 先找到该节点，通过遍历
(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nicknam

3.2. 代码实现

package Linkedlist;


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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //加入
        // singleLinkedList.add(hero1);
        // singleLinkedList.add(hero4);
        // singleLinkedList.add(hero2);
        // singleLinkedList.add(hero3);

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        // singleLinkedList.addByOrder(hero3);


        //显示一把
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();
    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为单列表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        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) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前链表
        }

        //判断flag的值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号 %d 已经存在了，不能添加\n", heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }


    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改. //说明
    //1. 根据 newHeroNode 的 no 来修改即可
    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.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }
    }


    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
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

运行结果：

在这里插入图片描述

4. 单链表节点的删除

4.1. 思路分析

思路分析示意图：

在这里插入图片描述

从单链表中删除一个节点的思路

先找到需要删除的这个节点的前一个节点 temp
temp.next = temp.next.next
被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

4.2. 代码实现

package Linkedlist;


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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //加入
        // singleLinkedList.add(hero1);
        // singleLinkedList.add(hero4);
        // singleLinkedList.add(hero2);
        // singleLinkedList.add(hero3);

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        // singleLinkedList.addByOrder(hero3);


        //显示一把
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();

        //删除一个节点
        System.out.println("删除后的链表情况~~");
        singleLinkedList.del(1);
        singleLinkedList.del(4);
        singleLinkedList.del(2);
        singleLinkedList.del(3);

        singleLinkedList.list();

    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为单列表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        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) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前链表
        }

        //判断flag的值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号 %d 已经存在了，不能添加\n", heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }


    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改. //说明
    //1. 根据 newHeroNode 的 no 来修改即可
    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.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }
    }

    
    
    //删除节点
    //思路
    //1. head 不能动，因此我们需要一个temp（辅助节点）找到待删除节点的前一个节
    //2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
    public void del(int no){
        HeroNode temp = head;
        boolean flag =false;//标识是否找到待删除的节点
        while(true){
            if(temp.next == null){//已经到链表的最后
                break;
            }
            if(temp.next.no == no){
            //找到的待刪除节点的前一个节点temp
            flag = true;
            break;
            }
            temp = temp.next;//temp后移
        }
        //判断flag
        if(flag){//找到
            //可以删除
            temp.next = temp.next.next;
        }else{
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }

    }



    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
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
215
216
217
218
219
220
221
222
223
224
225

运行结果：
在这里插入图片描述

5. 单链表常见面试题

5.1. 求单链表中有效节点的个数

功能实现：

//方法：获取单链表的节点个数（如果是带头节点的链表，那么久不统计头节点）
    /**
     * 
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if(head.next == null){//空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助变量,没有统计头节点
        HeroNode cur = head.next;
        while(cur != null) {
        	length++;
        	cur = cur.next;//遍历
        }
        return length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

完整代码实现：

package Linkedlist;


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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        // singleLinkedList.addByOrder(hero3);


        //显示一把
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();

        //删除一个节点
        System.out.println("删除后的链表情况~~");
        singleLinkedList.del(1);
        singleLinkedList.del(4);
//        singleLinkedList.del(2);
//        singleLinkedList.del(3);

        singleLinkedList.list();

        //求单链表中有效节点个数
        System.out.println("有效的节点个数 = " + getLength(singleLinkedList.getHead()));
        
    }

    //方法：获取单链表的节点个数（如果是带头节点的链表，那么久不统计头节点）
    /**
     * 
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if(head.next == null){//空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助变量,没有统计头节点
        HeroNode cur = head.next;
        while(cur != null) {
        	length++;
        	cur = cur.next;//遍历
        }
        return length;
    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //返回头节点
    public HeroNode getHead() {
		return head;
	}



	//添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为单列表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        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) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前链表
        }

        //判断flag的值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号 %d 已经存在了，不能添加\n", heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }


    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改. //说明
    //1. 根据 newHeroNode 的 no 来修改即可
    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.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }
    }

    
    
    //删除节点
    //思路
    //1. head 不能动，因此我们需要一个temp（辅助节点）找到待删除节点的前一个节
    //2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
    public void del(int no){
        HeroNode temp = head;
        boolean flag =false;//标识是否找到待删除的节点
        while(true){
            if(temp.next == null){//已经到链表的最后
                break;
            }
            if(temp.next.no == no){
            //找到的待刪除节点的前一个节点temp
            flag = true;
            break;
            }
            temp = temp.next;//temp后移
        }
        //判断flag
        if(flag){//找到
            //可以删除
            temp.next = temp.next.next;
        }else{
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }

    }



    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249

运行结果：

在这里插入图片描述

5.2. 查找单链表中倒数第k个节点

（新浪面试题）

在这里插入图片描述

功能实现：

    //查找单链表中的倒数第k个节点【新浪面试题】
    //思路
    //1. 编写一个方法，接收head节点，同时接收一个index
    //2. index 表示是倒数第index个节点
    //3. 先把链表从头到尾遍历，得到链表的总长度getLength
    //4. 得到size(getLength)后，我们从链表的第一个开始遍历（size-index）个，就可以得到
    //5. 如果找到了，则返回该节点，否则返回null
    public static HeroNode findLastIndexNode(HeroNode head, int index){
        //判断如果链表为空，返回null
        if(head.next == null){
            return null;//没有找到
        }
        //第一次遍历得到链表的长度（节点个数）
        int size = getLength(head);

        //第二次遍历 size-index 位置
        //先做一个index的校验
        if(index <= 0 || index > size){
            return null;
        }
        //定义一个辅助变量,for循环定位到倒数的index
        HeroNode cur = head.next;//假设链表有3个数据，查找倒数第一个数据，那么size-index=3-1=2
        for(int i = 0; i < size - index; i++){
            cur = cur.next;
        }
        return cur;

    }
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

完整代码实现：

package Linkedlist;


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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        // singleLinkedList.addByOrder(hero3);
        
        //显示链表
        singleLinkedList.list();

        System.out.println("--------------------------------");
        //查找倒数第k个节点
        HeroNode result = findLastIndexNode(singleLinkedList.getHead(), 1);
        System.out.println("result=" + result);
        
    }

    //查找单链表中的倒数第k个节点【新浪面试题】
    //思路
    //1. 编写一个方法，接收head节点，同时接收一个index
    //2. index 表示是倒数第index个节点
    //3. 先把链表从头到尾遍历，得到链表的总长度getLength
    //4. 得到size(getLength)后，我们从链表的第一个开始遍历（size-index）个，就可以得到
    //5. 如果找到了，则返回该节点，否则返回null
    public static HeroNode findLastIndexNode(HeroNode head, int index){
        //判断如果链表为空，返回null
        if(head.next == null){
            return null;//没有找到
        }
        //第一次遍历得到链表的长度（节点个数）
        int size = getLength(head);

        //第二次遍历 size-index 位置
        //先做一个index的校验
        if(index <= 0 || index > size){
            return null;
        }
        //定义一个辅助变量,for循环定位到倒数的index
        HeroNode cur = head.next;//假设链表有3个数据，查找倒数第一个数据，那么size-index=3-1=2
        for(int i = 0; i < size - index; i++){
            cur = cur.next;
        }
        return cur;

    }

    //方法：获取单链表的节点个数（如果是带头节点的链表，那么久不统计头节点）
    /**
     * 
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if(head.next == null){//空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助变量,没有统计头节点
        HeroNode cur = head.next;
        while(cur != null) {
        	length++;
        	cur = cur.next;//遍历
        }
        return length;
    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //返回头节点
    public HeroNode getHead() {
		return head;
	}



	//添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为单列表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        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) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前链表
        }

        //判断flag的值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号 %d 已经存在了，不能添加\n", heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }


    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改. //说明
    //1. 根据 newHeroNode 的 no 来修改即可
    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.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }
    }

    
    
    //删除节点
    //思路
    //1. head 不能动，因此我们需要一个temp（辅助节点）找到待删除节点的前一个节
    //2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
    public void del(int no){
        HeroNode temp = head;
        boolean flag =false;//标识是否找到待删除的节点
        while(true){
            if(temp.next == null){//已经到链表的最后
                break;
            }
            if(temp.next.no == no){
            //找到的待刪除节点的前一个节点temp
            flag = true;
            break;
            }
            temp = temp.next;//temp后移
        }
        //判断flag
        if(flag){//找到
            //可以删除
            temp.next = temp.next.next;
        }else{
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }

    }



    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263

运行结果：

在这里插入图片描述

5.3. 单链表的反转

（腾讯面试题）
在这里插入图片描述

分析思路：
将原来链表中的第一个节点放到新链表的第一个位置（节点head后面），然后将原来第二个节点放到新链表的第一个位置（这样图中的数据5就在数据2前面了），再将数据5的next指向数据2。同理插入数据9。最后形成的新链表就是原链表反转的结果。

功能实现：

    //将单链表反转
    public static void reversetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null){
            return;
        }

        //定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        while (cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点，后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;
            cur = next;//让cur后移
        }
        //将head.next 指向reverseHead.next，实现单链表的反转
        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

完整代码实现：

package Linkedlist;


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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //加入
        // singleLinkedList.add(hero1);
        // singleLinkedList.add(hero4);
        // singleLinkedList.add(hero2);
        // singleLinkedList.add(hero3);

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        // singleLinkedList.addByOrder(hero3);

        //显示链表
        singleLinkedList.list();

        System.out.println("--------------------------------");
        reversetList(singleLinkedList.getHead());
        singleLinkedList.list();
    }

    //将单链表反转
    public static void reversetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null){
            return;
        }

        //定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        while (cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点，后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;
            cur = next;//让cur后移
        }
        //将head.next 指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }


    //查找单链表中的倒数第k个节点【新浪面试题】
    //思路
    //1. 编写一个方法，接收head节点，同时接收一个index
    //2. index 表示是倒数第index个节点
    //3. 先把链表从头到尾遍历，得到链表的总长度getLength
    //4. 得到size(getLength)后，我们从链表的第一个开始遍历（size-index）个，就可以得到
    //5. 如果找到了，则返回该节点，否则返回null
    public static HeroNode findLastIndexNode(HeroNode head, int index){
        //判断如果链表为空，返回null
        if(head.next == null){
            return null;//没有找到
        }
        //第一次遍历得到链表的长度（节点个数）
        int size = getLength(head);

        //第二次遍历 size-index 位置
        //先做一个index的校验
        if(index <= 0 || index > size){
            return null;
        }
        //定义一个辅助变量,for循环定位到倒数的index
        HeroNode cur = head.next;//假设链表有3个数据，查找倒数第一个数据，那么size-index=3-1=2
        for(int i = 0; i < size - index; i++){
            cur = cur.next;
        }
        return cur;

    }

    //方法：获取单链表的节点个数（如果是带头节点的链表，那么久不统计头节点）
    /**
     * 
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if(head.next == null){//空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助变量,没有统计头节点
        HeroNode cur = head.next;
        while(cur != null) {
        	length++;
        	cur = cur.next;//遍历
        }
        return length;
    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //返回头节点
    public HeroNode getHead() {
		return head;
	}



	//添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为单列表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        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) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前链表
        }

        //判断flag的值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号 %d 已经存在了，不能添加\n", heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }


    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改. //说明
    //1. 根据 newHeroNode 的 no 来修改即可
    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.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }
    }

    
    
    //删除节点
    //思路
    //1. head 不能动，因此我们需要一个temp（辅助节点）找到待删除节点的前一个节
    //2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
    public void del(int no){
        HeroNode temp = head;
        boolean flag =false;//标识是否找到待删除的节点
        while(true){
            if(temp.next == null){//已经到链表的最后
                break;
            }
            if(temp.next.no == no){
            //找到的待刪除节点的前一个节点temp
            flag = true;
            break;
            }
            temp = temp.next;//temp后移
        }
        //判断flag
        if(flag){//找到
            //可以删除
            temp.next = temp.next.next;
        }else{
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }

    }



    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290

运行结果：

在这里插入图片描述

5.4. 从尾到头打印单链表

（百度面试题）

做这道题之前先学习栈：

代码示例：

package Linkedlist;

import java.util.Stack;

//stack的基本使用
public class TestStack {
    public static void main(String[] args){
        Stack<String> stack = new Stack();

        //入栈
        stack.add("jack");
        stack.add("tom");
        stack.add("smith");

        //出栈顺序：smith,tom,jack
        while (stack.size() > 0) {
        System.out.println(stack.pop());//pop就是将栈顶的数据取出
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果：
在这里插入图片描述

思路分析：

在这里插入图片描述

思路
上面的题的要求就是逆序打印单链表.
方式1：先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议
方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果。

功能实现：

//逆序打印单链表
    //方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
    public static void reversePrint(HeroNode head){
        if (head.next == null) {
            return;//空链表，不能打印
        }
        //创建一个栈，将节点压入栈中
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;

        //将链表的所有节点压入栈
        while(cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        //将栈中的节点进行打印。pop出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
            
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

完整代码实现：

package Linkedlist;

import java.net.http.HttpHeaders;
import java.util.Stack;

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, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        // singleLinkedList.addByOrder(hero3);

        //显示链表
        singleLinkedList.list();

        System.out.println("-----------逆序打印，没有改变链表的结构--------------");
        reversePrint(singleLinkedList.getHead());
    }

    //逆序打印单链表
    //方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
    public static void reversePrint(HeroNode head){
        if (head.next == null) {
            return;//空链表，不能打印
        }
        //创建一个栈，将节点压入栈中
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;

        //将链表的所有节点压入栈
        while(cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        //将栈中的节点进行打印。pop出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
            
        }
    }


    //将单链表反转
    public static void reversetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null){
            return;
        }

        //定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        while (cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点，后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur;
            cur = next;//让cur后移
        }
        //将head.next 指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }


    //查找单链表中的倒数第k个节点【新浪面试题】
    //思路
    //1. 编写一个方法，接收head节点，同时接收一个index
    //2. index 表示是倒数第index个节点
    //3. 先把链表从头到尾遍历，得到链表的总长度getLength
    //4. 得到size(getLength)后，我们从链表的第一个开始遍历（size-index）个，就可以得到
    //5. 如果找到了，则返回该节点，否则返回null
    public static HeroNode findLastIndexNode(HeroNode head, int index){
        //判断如果链表为空，返回null
        if(head.next == null){
            return null;//没有找到
        }
        //第一次遍历得到链表的长度（节点个数）
        int size = getLength(head);

        //第二次遍历 size-index 位置
        //先做一个index的校验
        if(index <= 0 || index > size){
            return null;
        }
        //定义一个辅助变量,for循环定位到倒数的index
        HeroNode cur = head.next;//假设链表有3个数据，查找倒数第一个数据，那么size-index=3-1=2
        for(int i = 0; i < size - index; i++){
            cur = cur.next;
        }
        return cur;

    }

    //方法：获取单链表的节点个数（如果是带头节点的链表，那么久不统计头节点）
    /**
     * 
     * @param head
     * @return
     */
    public static int getLength(HeroNode head){
        if(head.next == null){//空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助变量,没有统计头节点
        HeroNode cur = head.next;
        while(cur != null) {
        	length++;
        	cur = cur.next;//遍历
        }
        return length;
    }
}

//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, null, null);

    //返回头节点
    public HeroNode getHead() {
		return head;
	}



	//添加节点到单向链表
    //思路：当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next指向新的节点
    public void add (HeroNode heroNode){

        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if(temp.next == null){
                break;
            }
            //如果没有找到 最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }


    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode){
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为单列表，我们找的temp是位于添加位置的前一个节点，否则插入不了
        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) {//说明希望添加的heroNode的编号已经存在
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;//后移，遍历当前链表
        }

        //判断flag的值
        if (flag) {//不能添加，说明编号存在
            System.out.printf("准备插入的英雄编号 %d 已经存在了，不能添加\n", heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }


    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改. //说明
    //1. 根据 newHeroNode 的 no 来修改即可
    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.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }
    }

    
    
    //删除节点
    //思路
    //1. head 不能动，因此我们需要一个temp（辅助节点）找到待删除节点的前一个节
    //2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
    public void del(int no){
        HeroNode temp = head;
        boolean flag =false;//标识是否找到待删除的节点
        while(true){
            if(temp.next == null){//已经到链表的最后
                break;
            }
            if(temp.next.no == no){
            //找到的待刪除节点的前一个节点temp
            flag = true;
            break;
            }
            temp = temp.next;//temp后移
        }
        //判断flag
        if(flag){//找到
            //可以删除
            temp.next = temp.next.next;
        }else{
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }

    }



    //显示链表[遍历]
    public void list(){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }

        //因为头节点不能动，每个HeroNode对象就是一个节点
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if(temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将next后移。（不后移就成了死循环，一定小心）
            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 Nickname){
        this.no = No;
        this.name = Name;
        this.nickname = Nickname;
    }

    //为了显示方便，我们重写toString
    @Override
    public String toString() {
        // return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + ", next = " + next + "]";
        return "HeroNode [no = " + no + ", name = " + name + ", nickname = " + nickname + "]";
    }
}
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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309

运行结果：

在这里插入图片描述

相关阅读:
使用 Redux 管理全局状态
 大语言模型之十二 SentencePiece扩充LLama2中文词汇
 Acrel-3000WEB电能管理系统在都巴高速的应用
 👋 和我一起学 Three.js【初级篇】：0. 总论
 Rancher 2.x集群销毁及卸载清理
 不卖硬件只卖软件的“能源管理系统”，都是骗子
 Linux(Centos)防火墙允许通过端口增加操作记录
 读书笔记-深度记忆
 嵌入式硬件中常见的面试问题与实现
 微信聚合聊天，自动回复
原文地址：https://blog.csdn.net/weixin_44883789/article/details/134475417

【数据结构(二)】单链表（3）

文章目录

1. 链表介绍

2. 单链表应用实例

2.1. 顺序添加方式

2.1.1. 思路分析

2.1.2. 代码实现

2.2. 按照编号顺序添加方式

2.2.1. 思路分析

2.2.2. 代码实现

3. 单链表节点的修改

3.1. 思路分析

3.2. 代码实现

4. 单链表节点的删除

4.1. 思路分析

4.2. 代码实现

5. 单链表常见面试题

5.1. 求单链表中有效节点的个数

5.2. 查找单链表中倒数第k个节点

5.3. 单链表的反转

5.4. 从尾到头打印单链表