链表

luffy 5/24/2023 data-structure

# 三、链表

# 1、链表(Linked List)介绍

链表是以节点的方式来存储,是链式存储
每一个结点包含 data 域、next 域。其中 next 域存放的是下一个结点的地址(双向链表还有一个 prev)
如图：发现链表的各个节点不一定是连续存储.

链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单链表(带头结点) 逻辑结构示意图如下

代码描述节点:

public ListNode{
   public int age;				// 本结点的信息
   public String name;
   public ListNode next; 		// 下一个结点的地址
}

1
2
3
4
5

# 2、单链表的应用实例

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作

# Ⅰ-添加方法一:在添加英雄时，直接添加到链表的尾部

思路分析示意图:
演示最基础的链表插入:插入到链表的最后面,不考虑顺序
- 首先我们需要创建一个头结点，该结点的作用就是表示单链表的头，如果没有头结点，我们是无法知道链表的首个结点是谁、在哪；
- 单链表是单向的，所以我们需要从头结点开始遍历整个链表直到末尾，然后增加结点到链表的末尾；
- 需要注意的是，头结点是万万不能乱动的，所以我们最好将头结点复制到一个临时结点变量中，对临时变量进行遍历。
代码示例:

package com.linkedlist.firstadd;
/**
 * 演示最基础的链表插入,插入到链表的最后面,不考虑顺序
 */
public class FirstAdd {
    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.list();
    }
}

//一、定义一个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;里不打印next,是因为如果这样打印的话,会将整个链表全部打印出来
    @Override
    public String toString() {
        return "HeroNode[no=" + no + ",name=" + name + ",nickname=" + nickname + "]";
    }

}
//二、定义SingleLinkedList管理我们的英雄
class SingleLinkedList {
    //1. 先初始化一个头节点,头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");
    //2. 返回头节点,get方法
    public HeroNode getHead() {
        return head;
    }

    /**
     * 3. 添加节点到单链表后
     * 思路:不考虑编号顺序,直接插入到链表最后
     * 1)找到当前链表的最后节点
     * 2)将最后这个节点的next指向新的节点
     */
    public void add(HeroNode heroNode) {
        //因为head节点是不能动的,动了的话链表就找不到入口或者找错路口,所以我们需要一个辅助遍历
        HeroNode temp = head;
        //遍历链表,找到最后
        while (true) {
            //找到链表的最后:当next值为空,就是最后一位
            if (temp.next == null) break;
            //如果没有找到最后,就将temp向后移动,不然就原地踏步死循环了
            temp = temp.next;
        }
        //当退出while循环的时候,temp就指向了链表的最后
        //将最后这个节点的next指向新的节点
        temp.next = heroNode;
    }

    //4. 显示链表[遍历]
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动且头节点是没有数据的,所以直接`head.next;`
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) break;
            //输出节点信息
            System.out.println(temp);
            //将temp后移,一定小心
            temp = temp.next;
        }
    }
}

# Ⅱ-添加方法二:根据排名将英雄插入到指定位置

如果有这个排名(即 no 重复)，则添加失败，并给出提示
思路分析示意图:

代码中实例场景示例图:

思路分析:
- 首先还是要创建一个头结点，然后拷贝一个头结点作为辅助变量，使用辅助变量来遍历整个链表；
- 如果出现某个结点（假设是 A 结点）的下一个结点（假设是 B 结点）的编号大于待插入结点的情况，那么就首先将 B 结点记录在待插入的结点中，然后再将这个待插入结点插入到 A 结点之后；
- 如果遍历到了链表末尾还没找到编号更大的，就直接插入到末尾即可。
代码实现:(只是将第一方法代码示例中的 add()替换未 addByOrder)

    public void addByOrder(HeroNode heroNode) {
    /*因为head节点是不能动的,动了的话链表就找不到入口或者找错路口,所以我们需要一个辅助遍历
       因为单链表,所以我们找的temp 必须为于添加位置的前一个节点,否则插入不了*/
        HeroNode temp = head;
        boolean flag = false; //flag标识添加的编号是否存在,默认为false
        while (true) {
            if (temp.next == null) break;//说明temp已经在链表的最后,就在链表插入(此时temp已经在链表尾部了)
            if (temp.next.no > heroNode.no) break;//说明位置已经找到,就在temp的后面插入
            else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode编号已经存在
                flag = true;
                break;
            }
            temp = temp.next;//temp后移,直到找到符合上面条件为止
        }
        if (flag) System.out.printf("准备插入的英雄的编号%d已经存在了,不能加入\n", heroNode.no);
        else {
            //将heroNode插入到链表的temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

-------------- main()中调用  ------------------------
 singleLinkedList.addByOrder(hero2);
 singleLinkedList.addByOrder(hero4);
 singleLinkedList.addByOrder(hero4);

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

# Ⅲ-修改节点

思路(1) 先找到该节点，通过遍历，(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname
- 首先还是要创建一个头结点，然后拷贝一个头结点作为辅助变量，使用辅助变量来遍历整个链表；
- 遍历过程中，比对每个结点的编号与要更新的结点的编号是否一致，如果一致则说明找到了要更新的结点。接着将找到的结点中的数据替换成要更新的数据即可；
- 如果遍历结束还没找到对应编号的结点，说明链表中不存在这个结点
代码实现

  //5. 修改节点信息,根据no编号来修改,即no编号不能改
    public void update(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        ;
        //定义一个辅助变量
        HeroNode temp = head;
        boolean flag = false;
        //找到需要修改的节点,根据no编号
        while (true) {
            if (temp == null) break; //表示当前到链表尾端
            if (temp.no == newHeroNode.no) {//表示找到该节点了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {//根据flag可以判断是否找到要修改的节点
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else System.out.printf("没有找到编号%d的阶段,不能进行修改\n", newHeroNode.no);
    }
----------------- main()调用测试 ----------------------------------------
  //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);
        System.out.println("测试修改后的");
        singleLinkedList.list();

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

# Ⅳ-删除节点

思路分析:
- 其实就是方法二中实例场景示例图的逆推
- 首先还是要创建一个头结点，然后拷贝一个头结点作为辅助变量，使用辅助变量来遍历整个链表；
- 如果遍历到某个结点的编号与要查找的给定的编号相同，那么就找到了结点；
- 如果遍历结束还没找到，说明该编号不在链表的结点中。
代码示例

   //6. 删除节点1.head不能动,所以需要一个temp辅助节点找到待删除节点前的一个节点
    //         2.我们比较时,时temp.next.no和待删除节点的no比较
    public void del(int no) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        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后移,遍历
        }
        if (flag) temp.next=temp.next.next; //如果找到,进行删除
        else System.out.printf("要删除的%d节点不存在\n",no);
    }
----------------- main()调用 ------------------------------
   //删除一个节点
    singleLinkedList.del(1);
    singleLinkedList.del(4);
    System.out.println("删除后的链表情况~~");
    singleLinkedList.list();

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

# Ⅴ-全部代码

package com.luffy.stack;

/**
 * @author dreamLuffe
 * @data 2023/5/22 14:49
 */
public class SecondAdd {
   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();
       //1. 不按顺序添加:方法一
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
       //2. 添加方法二
       singleLinkedList.addByOrder(hero1);
       singleLinkedList.addByOrder(hero3);
       singleLinkedList.addByOrder(hero2);
       singleLinkedList.addByOrder(hero4);
       singleLinkedList.addByOrder(hero4);
       //调用打印
       singleLinkedList.list();
       //3. 测试修改节点的代码
       HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
       singleLinkedList.update(newHeroNode);
       System.out.println("测试修改后的");
       singleLinkedList.list();
       //4. 删除一个节点
       singleLinkedList.del(1);
       singleLinkedList.del(4);
       System.out.println("删除后的链表情况~~");
       singleLinkedList.list();
   }

   /**-------下面 `面试题部分`方法可以放在这个地方进行运行 编写的是静态方法----------------*/
    public static int getLength(HeroNode head) {...}
    public static HeroNode findLastIndexNode(HeroNode head, int K) {}
    public static void reverseLinkedHead(HeroNode head) {}
    public static void reversePrint(HeroNode head) {}
   /**-------下面 `面试题部分`方法可以放在这个地方进行运行----------------*/
}

//一、定义一个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 + "]";
   }

}

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

   //2. 返回头节点,get方法  这个方法是配合下面面试题时使用,使外面也能获得私有变量
   public HeroNode getHead() {
       return head;
   }

   /**
    * 3. 添加节点到单链表后-----------------弃用的,用来对比`addByOrder()`
    * 思路:不考虑编号顺序,直接插入到链表最后
    * 1)找到当前链表的最后节点
    * 2)将最后这个节点的next指向新的节点
    */
   public void add(HeroNode heroNode) {
       //因为head节点是不能动的,动了的话链表就找不到入口或者找错路口,所以我们需要一个辅助遍历
       HeroNode temp = head;
       //遍历链表,找到最后
       while (true) {
           //找到链表的最后:当next值为空,就是最后一位
           if (temp.next == null) break;
           //如果没有找到最后,就将temp向后移动,不然就原地踏步死循环了
           temp = temp.next;
       }
       //当退出while循环的时候,temp就指向了链表的最后
       //将最后这个节点的next指向新的节点
       temp.next = heroNode;
   }

   //4. 添加节点到单链表后,按no排序
   public void addByOrder(HeroNode heroNode) {
   /*因为head节点是不能动的,动了的话链表就找不到入口或者找错路口,所以我们需要一个辅助遍历
      因为单链表,所以我们找的temp 必须为于添加位置的前一个节点,否则插入不了*/
       HeroNode temp = head;
       boolean flag = false; //flag标识添加的编号是否存在,默认为false
       while (true) {
           if (temp.next == null) break;//说明temp已经在链表的最后,就在链表插入(此时temp已经在链表尾部了)
           if (temp.next.no > heroNode.no) break;//说明位置已经找到,就在temp的后面插入
           else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode编号已经存在
               flag = true;
               break;
           }
           temp = temp.next;//temp后移,直到找到符合上面条件为止
       }
       if (flag) System.out.printf("准备插入的英雄的编号%d已经存在了,不能加入\n", heroNode.no);
       else {
           //将heroNode插入到链表的temp后面
           heroNode.next = temp.next;
           temp.next = heroNode;
       }
   }

   //5. 修改节点信息,根据no编号来修改,即no编号不能改
   public void update(HeroNode newHeroNode) {
       if (head.next == null) {
           System.out.println("链表为空");
           return;
       }
       ;
       //定义一个辅助变量
       HeroNode temp = head;
       boolean flag = false;
       //找到需要修改的节点,根据no编号
       while (true) {
           if (temp == null) break; //表示当前到链表尾端
           if (temp.no == newHeroNode.no) {//表示找到该节点了
               flag = true;
               break;
           }
           temp = temp.next;
       }
       if (flag) {//根据flag可以判断是否找到要修改的节点
           temp.name = newHeroNode.name;
           temp.nickname = newHeroNode.nickname;
       } else System.out.printf("没有找到编号%d的阶段,不能进行修改\n", newHeroNode.no);
   }

   //6. 删除节点1.head不能动,所以需要一个temp辅助节点找到待删除节点前的一个节点
   //         2.我们比较时,时temp.next.no和待删除节点的no比较
   public void del(int no) {
//        if (head.next == null) {
//            System.out.println("链表为空");
//            return;
//        }此处可以不加,与下面代码功能重复
       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后移,遍历
       }
       if (flag) temp.next = temp.next.next; //如果找到,进行删除
       else System.out.printf("要删除的%d节点不存在\n", no);
   }

   //7. 显示链表[遍历]
   public void list() {
       //判断链表是否为空
       if (head.next == null) {
           System.out.println("链表为空");
           return;
       }
       //因为头节点不能动且头节点是没有数据的,所以直接`head.next;`
       HeroNode temp = head.next;
       while (true) {
           if (temp == null) break;
           //输出节点信息
           System.out.println(temp);
           //将temp后移,一定小心
           temp = 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
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

# 3、单链表面试题

单链表的常见面试题有如下:

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

2)查找单链表中的倒数第 k 个结点【新浪面试题】

3)单链表的反转【腾讯面试题，有点难度】

4)从尾到头打印单链表【百度，要求方式 1：反向遍历。方式 2：Stack 栈】

5)合并两个有序的单链表，合并之后的链表依然有序【课后练习.】

以下例子将在 2 部分的全部代码中实现,在上面代码中已经预留位置

# Ⅰ-求单链表中有效节点的个数

就是直接遍历没得分析,直接上代码:

 /**
    * 1. 求单链表中有效节点的个数
    * 方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
    * @param head 链表的头节点
    * @return 返回的就是有效节点的个数
    */
   public static int getLength(HeroNode head) {
       if (head.next == null) return 0; //空链表
       int length = 0; //声明一个累加器
       //定义一个辅助的变量,这里我们没有统计头节点(-->head.next)
       HeroNode cur = head.next;
       while (cur != null) {//当当前节点 为空时退出累计遍历
           length++;
           cur = cur.next;
       }
       return length;
   };
-----------------main()调用  ---------------------------
System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));//2

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

# Ⅱ-查找单链表中的倒数第 k 个结点【新浪面试题】

思路分析:

1)编写一个方法，接收 head 节点，同时接收一个 K

2)K 表示是倒数第 K 个节点

3)先把链表从头到尾遍历，得到链表的总的长度 getLength

4)得到 size 后，我们从链表的第一个开始遍历 (size-K)个，就可以得到

5)如果找到了，则返回该节点，否则返回 null
代码示例:

    /**2.查找单链表中的倒数第k个结点
     * @param head 要进行查找的单向链表
     * @param K 传入倒数第几位 数字
     * @return 该位置的节点
     */
    public static HeroNode findLastIndexNode(HeroNode head, int K) {
        if (head.next == null) return null; //空链表,无法找到
        //1. 获得链表的长度(总个数)
        int size = getLength(head);
        //2. 做一个K的校验,明显K不能为负数以及大于总长度
        if (K <= 0 || K > size) return null;
        //3. 定义给辅助变量
        HeroNode cur = head.next;
        //4. 遍历 倒数第K个节点 就是`size-K`的位置
        for (int i = 0; i < (size - K); i++) {
            cur = cur.next; //cur后移到符合条件的位置
        }
        return cur;
    }
-----------------main()调用  ---------------------------
 //测试一下看看是否得到了倒数第K个节点
 HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
 System.out.println("res=" + res);

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

# Ⅲ-单链表的反转【腾讯面试题，有点难度】

解决这个问题的核心就是头插法。
- 首先创建一个临时头结点用于记录反转过程中的链表；
- 遍历单链表，每遍历到一个有效结点，就让该有效结点指向临时头结点指向的结点；
- 临时头结点再指向该有效结点，
- 原单链表遍历结束之后，再让原头结点指向临时头结点指向的结点。
图片示例:
具体举例图解
代码实现:

实现方法一:

    /**
       * 3.单链表的反转【腾讯面试题，有点难度】
       * @param head 传入需要进行反转的单链表
       */
      public static void reverseLinkedHead(HeroNode head) {
           //1. 当链表为空或者只有一个节点时候,直接返回,无需反转
          if (head.next == null || head.next.next == null) return;
           //2. 定义一个辅助的指针遍历,帮助我们遍历原来的链表
           HeroNode cur = head.next;
           //3. 定义一个next,辅助变量,来指向当前节点[cur]的下一个节点,用来进行位置互换
           HeroNode next = null;
           //4. 初始化一个新的头节点,用来暂时存放反转链表
           HeroNode reverseHead = new HeroNode(0, "", "");
           //5. 遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead的最前端
           while (cur != null) {//当当前节点 为空时退出累计遍历
               next = cur.next; //先暂时保存当前节点的下一个节点,后面换完位置后需要复原cur的下一位,否则无法遍历
               cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
               reverseHead.next = cur;//将cur链接到新的链表上
               cur = next;//让cur后移
           }
           //遍历结束,将head.next指向reverseHead.next 接管链表,实现单链表的反转
           head.next = reverseHead.next;
       }
   -----------------main()调用  ---------------------------
      //7. 测试一下单链表的反转功能
   	System.out.println("原来链表的情况~~");
   	singleLinkedList.list();
   	System.out.println("反转单链表~~");
   	reverseLinkedHead(singleLinkedList.getHead());
   	singleLinkedList.list();

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

实现方法二(只是写法改变,但代码显得更容易理解):

/**
 * 单链表的反转
 */
public SingleLinkedList reverse() {
   SingleLinkedList linkedList = new SingleLinkedList();
    // 遍历待反转的链表，将结点依次添加到新链表
   Node tmp = head;
    while (tmp.next != null) {
        linkedList.addFirst(tmp.next.item);
        tmp = tmp.next;
    }
    return linkedList;
}
public boolean addFirst(Integer item) {
    Node newNode = new Node(item, null);
    // tmp 指向头结点
    Node tmp = head;
    newNode.next = tmp.next;
    tmp.next = newNode;
    return true;
}

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

# Ⅳ-从尾到头打印单链表

【百度面试题，要求方式 1：反向遍历(上一个问题解决) 。方式 2：Stack 栈方法 3: 递归】
栈方法
思路分析图解:
代码示例:

  /**
   * 4. 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
   * @param head 要传入的链表头
   */
  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;//cur后移,这样就可以压入下一个节点
      }
      //将栈中节点取出打印.利用其先进后出特点,实现逆序da'yin
      while (stack.size() > 0) {
          System.out.println(stack.pop());
      }
  }
  -----------------main()调用  ---------------------------
 //8.测试逆序打印单链表, 没有改变链表的结构~~
 System.out.println("测试逆序打印单链表, 没有改变链表的结构~~");
 reversePrint(singleLinkedList.getHead());

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

递归方式
图例:
代码实现:

/**
 * 使用递归打印结点
 * @Param [node] 链表的第一个结点，即 head.next
 */
public static void printReverse_3(HeroNode node){
    // 这里一定要先递归调用再打印
    if (node.next != null){
        printReverse_3(node.next);
    }
    System.out.println(node);
}

1
2
3
4
5
6
7
8
9
10
11
12

# Ⅴ-合并两个有序的单链表，合并之后的链表依然有序

练习题目:合并两个有序的单链表，合并之后的链表依然有序

思路解析:
- 如果传入的节点 1 为空了(即已经递归到链表尾或者是空链表),返回节点 2,反之亦然(同时 return 会结束该递归函数(但是递归函数结束后接着 return,所以整个递归函数将会停止)并返回)。
- 判断 no 是否重复,如果重复就重新递归传入链表下一级 head2.next,不重复就传入 head2
- 递归其实都是在进行对于 head.next 的赋值,直到传入节点为空(符合前面两个判断条件),开始向外 return,此时逐层给 head.next 赋值,最后会返回到最外层函数返回值处,就是合并后的链表
代码实现

    /**
     * 合并两个单链表静态函数
     * @param head1 传入第一个链表头节点
     * @param head2 传入第二个链表头节点
     * @return 返回合并后的链表
     */
    public static HeroNode mergeLinkedList(HeroNode head1, HeroNode head2) {
        if (head1 == null) return head2; //此处是递归,不能按head.next==null进行判断,否则会造成数据丢失
        if (head2 == null)  return head1;
        if (head1.no <= head2.no) {
            //如果不加这个判断,如果两者的no相同,将会导致出现重复的数据(如两个),判断后进入递归
            //打印代码 System.out.println("head:"+head+",head.next:"+head.next);
            //打印结果 headHeroNode:[no=0,name=,nickname=],head.nextHeroNode:[no=0,name=,nickname=]
            head1.next = (head2.no != head1.no) ? mergeLinkedList(head1.next, head2)
              			  : mergeLinkedList(head1.next, head2.next);
            //head1.next= mergeLinkedList(head1.next, head2);  犯下的错误,导致数据重复
            return head1;
        } else {
            head2.next = mergeLinkedList(head1, head2.next);
            return head2;
        }
    }

    /**
     * 遍历打印静态链表
     * @param head 传入打印的链表头节点
     */
    public static void staticList(HeroNode head) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动且头节点是没有数据的,所以直接`head.next;`
        HeroNode temp = head.next;
        System.out.println("head" + head + ",head.next" + head.next);
        while (true) {
            if (temp == null) break;
            //输出节点信息
            System.out.println(temp);
            //将temp后移,一定小心
            temp = temp.next;
        }
    }
-------------------  main()调用 --------------------------------
  HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  HeroNode hero3 = new HeroNode(5, "洪吉林", "帅哥");
  HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  HeroNode hero5 = new HeroNode(5, "洪吉林", "帅哥");
  HeroNode hero6 = new HeroNode(6, "努力学习的汪", "好学生");
  HeroNode hero7 = new HeroNode(7, "离婚且带娃", "不是我");
  HeroNode hero8 = new HeroNode(8, "你听我狡辩", "口头禅");
      //创建链表对象
  SingleLinkedList singleLinkedList = new SingleLinkedList();
  SingleLinkedList singleLinkedList1 = new SingleLinkedList();
  //2. 添加方法
  singleLinkedList.addByOrder(hero1);
  singleLinkedList.addByOrder(hero3);
  singleLinkedList.addByOrder(hero4);
  singleLinkedList.addByOrder(hero7);
  singleLinkedList.list();
  System.out.println("两个链表分界线");
  //-----------课后作业:第二个链表-----------------------
  singleLinkedList1.addByOrder(hero2);
  singleLinkedList1.addByOrder(hero5);
  singleLinkedList1.addByOrder(hero6);
  singleLinkedList1.addByOrder(hero8);
  singleLinkedList1.list();
  System.out.println("合并两个链表");
  staticList(mergeLinkedList(singleLinkedList.getHead(), singleLinkedList1.getHead()));

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

# 4、双向链表与其实例

双向链表实现实际上对比单向链表多了一个 pre 属性,大部分功能相似
使用双向链表实现水浒传英雄增删改查思路图:

删除部分代码实现:

  /**
     * 5. 从双向链表中删除一个节点
     * 说明:
     * 1.对于双向链表,我们可以直接找到要删除的这个节点
     * 2.找到后,自我删除即可
     */
    public void del(int no) {
        if (head.next == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        DoubleHeroNode temp = head;//辅助遍历(指针)
        boolean flag = false;//标识是否找到待删除节点
        while (true) {
            if (temp == null) break;//已经到了链表最后
            if (temp.no == no) { //找到待删除的节点
                flag = true;
                break;
            }
            temp = temp.next;//temp后移,遍历
        }
        if (flag) {
            temp.pre.next = temp.next;//将下一个节点地址赋值给上一个节点的`next`
            //如果不加判断,可能当前节点是最后一个,导致`temp.next.pre`会出现空指针异常
            if (temp.next != null) temp.next.pre = temp.pre;//将下一个节点的上一个(pre)赋值为当前节点的上一个(pre)
        } else System.out.printf("要删除的%d节点不存在\n", no);

    }

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 com.linkedlist.doublelinked;
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleHeroNode hero1 = new DoubleHeroNode(1, "宋江", "及时雨");
        DoubleHeroNode hero2 = new DoubleHeroNode(2, "卢俊义", "玉麒麟");
        DoubleHeroNode hero3 = new DoubleHeroNode(3, "吴用", "智多星");
        DoubleHeroNode hero4 = new DoubleHeroNode(4, "林冲", "豹子头");
        DoubleHeroNode hero5 = new DoubleHeroNode(5, "666", "666");
        //创建链表对象
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        //1.直接添加到链表尾部
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
        doubleLinkedList.list();
        //修改测试
        System.out.println("测试修改林冲");
        DoubleHeroNode newHeroNode = new DoubleHeroNode(4, "洪吉林", "零充");
        doubleLinkedList.update(newHeroNode);
        doubleLinkedList.list();
        //删除测试
        System.out.println("测试删除吴用");
        doubleLinkedList.del(3);
        doubleLinkedList.list();
        //测试插入添加
        //1.直接添加到链表尾部
        System.out.println("测试插入添加 ");
        doubleLinkedList.addByOrder(hero5);
        doubleLinkedList.addByOrder(hero3);
        doubleLinkedList.list();
    }
}

class DoubleLinkedList {
    //1. 先初始化一个头节点,头节点不要动,不存放具体的数据
    private DoubleHeroNode head = new DoubleHeroNode(0, "", "");

    //2. 返回头节点,get方法
    public DoubleHeroNode getHead() {
        return head;
    }

    //3. 添加一个节点节点到双向链表的最后
    public void add(DoubleHeroNode heroNode) {
        //因为head节点是不能动的,动了的话链表就找不到入口或者找错路口,所以我们需要一个辅助遍历
        DoubleHeroNode temp = head;
        //遍历链表,找到最后
        while (true) {
            //找到链表的最后:当next值为空,就是最后一位
            if (temp.next == null) break;
            //如果没有找到最后,就将temp向后移动,不然就原地踏步死循环了
            temp = temp.next;
        }
        //当退出while循环的时候,temp就指向了链表的最后
        //形成一个双向链表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //3.1 按照no进行对双向链表的插入,课堂练习题
    public void addByOrder(DoubleHeroNode heroNode) {
        DoubleHeroNode temp = head;//需要找到要添加位置的前一个节点
        boolean flag = false;
        while (true) {
            if (temp.next == null) break;//说明已经遍历到链表最后
            if (temp.next.no > heroNode.no) break;//说明已经找到,就在temp后面插入
            else if (temp.next.no == heroNode.no) {//说明已经存在重复no
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) System.out.printf("准备插入的英雄的编号%d已经存在了,不能加入\n", heroNode.no);
        else {
            heroNode.next = temp.next; //将temp的下next赋值到要插入的节点的next
            heroNode.pre = temp;  //将temp作为heroNode的pre(上一位)
            temp.next = heroNode; //在找到的位置后面插入heroNode ,并且这里不用判断非空
        }
    }

    //4. 修改节点信息,
    //可以看到双向链表的节点内容修改与单向链表一样,只是节点类型改变
    public void update(DoubleHeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        DoubleHeroNode temp = head;
        boolean flag = false;
        //找到需要修改的节点,根据no编号
        while (true) {
            if (temp == null) break; //表示当前到链表尾端
            if (temp.no == newHeroNode.no) {//表示找到该节点了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {//根据flag可以判断是否找到要修改的节点
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else System.out.printf("没有找到编号%d的阶段,不能进行修改\n", newHeroNode.no);
    }

    /**
     * 5. 从双向链表中删除一个节点
     * 说明:
     * 1.对于双向链表,我们可以直接找到要删除的这个节点
     * 2.找到后,自我删除即可
     */
    public void del(int no) {
        if (head.next == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        DoubleHeroNode temp = head;//辅助遍历(指针)
        boolean flag = false;//标识是否找到待删除节点
        while (true) {
            if (temp == null) break;//已经到了链表最后
            if (temp.no == no) { //找到待删除的节点
                flag = true;
                break;
            }
            temp = temp.next;//temp后移,遍历
        }
        if (flag) {
            temp.pre.next = temp.next;//将下一个节点地址赋值给上一个节点的`next`
            //如果不加判断,可能当前节点是最后一个,导致`temp.next.pre`会出现空指针异常
            if (temp.next != null) temp.next.pre = temp.pre;//将下一个节点的上一个(pre)赋值为当前节点的上一个(pre)
        } else System.out.printf("要删除的%d节点不存在\n", no);

    }

    //7. 显示链表[遍历]
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动且头节点是没有数据的,所以直接`head.next;`
        DoubleHeroNode temp = head.next;
        while (true) {
            if (temp == null) break;
            //输出节点信息
            System.out.println(temp);
            //将temp后移,一定小心
            temp = temp.next;
        }
    }

}


//一、定义一个HeroNode,每个HeroNode对象就是一个节点
class DoubleHeroNode {
    public int no;
    public String name;
    public String nickname;
    public DoubleHeroNode next;//指向下一个节点,默认为null
    public DoubleHeroNode pre;//指向前一个节点,默认为null

    //构造器
    public DoubleHeroNode(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 + "]";
    }
}

# 5、单向与双向链表对比

管理单向链表相较于双向链表的缺点分析

① 单链表只有一个指向下一结点的指针，也就是只能 next; ② 双链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以通过 prev()快速找到前一结点，顾名思义，单链表只能单向读取
单向链表不能自我删除，需要靠辅助节点，而双向链表则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp,temp 是待删除节点的前一个节点,双向链表则是可以直接将 temp 指向要删除的节点

双链表具有以下优点:

删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样
查找时也一样，我们可以借用二分法的思路，从 head（首节点）向后查找操作和 last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍

面试官：从你的描述来看，双链表的在查找、删除的时候可以利用二分法的思想去实现,但是为什么目前市场应用上单链表的应用要比双链表的应用要广泛的多呢?

从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为 n 就需要 n*length（这个指针的 length 在 32 位系统中是 4 字节，在 64 位系统中是 8 个字节）的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这时一种工程总体上的衡量。

结构对比图

# 6、单链表之约瑟夫问题

# Ⅰ-问题描述:

约瑟夫（ Josephu ）问题是一个非常著名的有趣的题目。问题具体描述如下：

设编号分别为 1、2、3… n 的 n 个人围坐一圈，约定编号为 k（1≤k≤n）的人从 1 开始报数，数到 m 的那个人出列。出列的人的下一位又从 1 开始报数，数到 m 的那个人继续出列。以此类推，直到所有人都出列为止，由此产生一个出队编号的序列，这个序列也就是约瑟夫问题的解。

下面将用一个动图来描述一下这个问题

假设有 4 个人围坐一圈，约定编号为 1 的人开始报数，数到 3 的那个出列。最后产生的出队编号的序列将会是：3、2、4、1。

# Ⅱ-老师给的思路实现

用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。
约瑟夫问题-创建环形链表的思路图解

约瑟夫问题-小孩出圈的思路分析图

代码实现:

package com.linkedlist.josepfu;

public class Josepfu {
    public static void main(String[] args) {
       int NUM=5;// 加入5个小孩节点
        // 测试一把看看构建环形链表，和遍历是否ok
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(NUM);
        circleSingleLinkedList.showBoy();
        //测试一把小孩出圈是否正确
        circleSingleLinkedList.countBoy(1, 2, NUM); // 2->4->1->5->3
    }
}

//二、创建一个环形的单向链表
class CircleSingleLinkedList {
    //1. 创建一个first节点,当前没有编号
    private Boy first = null;

    //2. 添加小孩节点,构建成一个环形的链表
    public void addBoy(int nums) {
        //nums做一个数据校验
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        Boy curBoy = null; //辅助指针,帮助构建环形链表
        //使用for来创建我们的环形链表
        for (int i = 1; i <= nums; i++) {//i从1开始,才能得到编号与数字顺序一样的no;
            //根据编号创建小孩节点
            Boy boy = new Boy(i);
            if (i == 1) { //如果fori从0开始遍历,这里也要改为i==0,否则下面 `curBoy.setNext(boy);`将空指针异常
                first = boy;
                first.setNext(first); //构成环,即只有一个时自己指向自己
                curBoy = first;
            } else {
                boy.setNext(first); //将当前次循环的next指向第一个节点形成环
                curBoy.setNext(boy);//此处curBoy标记的是上一次循环的boy 如`i==2`-->curBoy==first、`i==3`-->curBoy==boy(第二个)
                curBoy = boy;  //这一步是移动当前curBoy位置到boy,保存当前boy 用作在下轮循环中指定当前boy的next
            }
        }
    }

    //3. 遍历当前环形链表
    public void showBoy() {
        if (first == null) {
            System.out.println("没有任何小孩~~~~");
            return;
        }
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩编号%d\n", curBoy.getNo());
            if (curBoy.getNext() == first) break;
            curBoy = curBoy.getNext();//curBoy后移
        }
    }

    /**
     * //4. 根据用户输入,计算小孩出圈的顺序
     *
     * @param startNo  开始的位置
     * @param countNum 每次循环的数字
     * @param nums     单纯用来校验循环次数是否多于总长度
     */
    public void countBoy(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误,请重新输入");
            return;
        }
        //①创建一个辅助指针,帮助完成小孩出圈
        Boy helper = first;
        //②将辅助指针事先指向环形列表的最后这个节点(即next指向first)
        while (true) {
            if (helper.getNext() == first) break;//说明helper指向最后的小孩节点
            helper = helper.getNext();
        }
        //③小孩报数前,先让first和helper移动K-1次(如果我是从3开始,我需要事先指向3的位置)
        //为什么是K-1次-->因为循环i是从0开始的
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //④出圈删除:当小孩报数时,让first和helper指针同时移动m-1次,然后出圈
        while (true) {
            if (helper == first) break; //说明圈中只有一个节点
            //让first和helper指针同时移动countNum-1次
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //出了for循环后,此时first指向的节点就是要出圈的小孩节点
            System.out.printf("小孩%d出圈\n", first.getNo());
            //此时将first指向的小孩节点出圈
            first = first.getNext();
           //注意:此处用的时setNext-->这步就是删除操作,原来的first指向的节点没有任何引用的时候,就会被回收
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号%d\n", first.getNo());
    }

}


//一、创建一个Boy类,表示一个节点
class Boy {
    private int no;//编号
    private Boy next; //指向下一个节点,默认null

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

# Ⅲ-思路改进与代码实现

思路解析:
- 首先要确定解决问题的核心思想：使用一个不带头结点的循环(环形)链表来处理该问题。
- 假设每个结点代表一个人，那么一个由 n 个结点组成的循环链表就相当于是 n 个人围成的一个圈。那么约瑟夫问题以环形链表的形式来描述就是如下情景：
- 首先使用 n 个结点构成一个单向循环链表，然后由第 k 个结点起从 1 开始计数，当计到 m 时，从链表中删除对应结点；接着从被删除结点的下一个结点开始从 1 计数，当计到 m 时，继续从链表中删除。依次循环往复，直到链表中的所有结点都被删除为止。
- 那么对于这个单向循环链表形式下的约瑟夫问题，我们如何解决呢？我们可以引入一个辅助指针 helperNode，这个指针总是指向待删除结点的前一个结点。为什么这个辅助指针要指向待删除结点的前一个结点，而不是指向自身呢？
- 因为我们的目的是要删除当前计数为 m 的结点，但是受限于单向链表的特性（如果要删除单链表的某个结点，必须要知道该结点的前一个结点），我们无法让结点自己删除自己。鉴于这个特性，我们必须要引入一个辅助指针来记录当前正在计数的结点的前一个结点，这样才能符合删除条件的结点从链表中删除。
引入这个辅助指针之后，具体的操作思路如下:

每一轮计数开始时，总让辅助指针 helperNode 初始指向本轮第一个计数的结点；
从第一个计数的结点开始计数至 m，实际上是向后移动了 m-1 个结点。由于辅助指针总是指向待删除结点的前一个结点，因此让需要让辅助指从第一个计数结点后移 m-2 个结点；
辅助指针移动到待删除结点的前一个结点之后，只需要让辅助指针指向待删除的结点的下一个结点即可完成删除操作；
依次循环往复，直至只剩最后一个结点；
对于环形链表判断是否只有最后一个结点，只需要判断辅助指针指向的结点是否是辅助指针指向的结点的下一个结点即可。

上面的思路可以用下面一个动图来描述:
代码实现

package com.linkedlist.doublelinked;
/**
 * 课程外思路实现
 */
public class DoubleLinkedListDemo2 {
    public static void main(String[] args) {
        // 构造测试数据
        HeroNode node_1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode node_2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode node_3 = new HeroNode(3, "吴用", "智多星");
        HeroNode node_4 = new HeroNode(4, "公孙胜", "入云龙");
        HeroNode node_5 = new HeroNode(5, "洪吉林", "码农");
        HeroNode node_6 = new HeroNode(6, "努力学习的汪", "学习狗");

        System.out.println("===============向环形链表中插入结点==================");
        HeroNode first = insertCircleList(null, node_1);
        first = insertCircleList(first, node_2);
        first = insertCircleList(first, node_3);
        first = insertCircleList(first, node_4);
        first = insertCircleList(first, node_5);
        first = insertCircleList(first, node_6);
        showList(first);

        System.out.println("===============约瑟夫游戏开始===============");
        // 从第 1 个结点开始计数，每次计 3 个数。
        josepfuGame(first, 1, 3);

    }

    /**
     * @Description 1. 约瑟夫游戏开始
     * @Param [first, k, m]   头节点,从第 k 个人开始数，每次数 m 个
     */
    public static void josepfuGame(HeroNode first, int k, int m) {
        if (first == null) {
            System.out.println("链表为空！");
            return;
        }
        HeroNode helperNode = first;
        // 首先要移动到第 k 个结点，此时辅助指针初始指向第一个计数的结点
        for (int i = 1; i < k; i++) {
            helperNode = helperNode.next;
        }
        while (helperNode.next.getNo() != helperNode.getNo()) {
            // 报数， m 个数也就是相当于向后移动 m-1 次，也就是要把第 m-1 个结点去掉
            // 由于单链表的特点，要去掉第 m-1 个结点，肯定是要让指针前一个结点，即第(m-2)个结点
            for (int j = 0; j < m - 2; j++) {  // 让指针后移 m-2 个结点
                helperNode = helperNode.next;
            }
            System.out.println(helperNode.next + "退出链表了!");
            // 删除结点
            helperNode.next = helperNode.next.next;
            // 因为下一轮要从刚刚去掉的结点的后面一个结点开始计数了，所以需要让辅助指针初始指向下一轮第一个计数的结点
            helperNode = helperNode.next;
        }
        System.out.println(helperNode + "退出链表了!");
    }

    /**
     * @Description 2. 插入结点到环形链表中，用于构造环形链表
     */
    public static HeroNode insertCircleList(HeroNode first, HeroNode node) {
        // 判断链表是不是为空，如果为空，就直接插入
        if (first == null) {
            first = node;
            // 因为要环形链表，而且只有一个结点，所以要我指向我自己
            first.next = node;
        } else {
            // 如果环形链表不为空
            HeroNode tempNode = first;
            while (true) {
                // 如果到了环形链表的最后一个元素
                if (tempNode.next.getNo() == first.getNo()) {
                    tempNode.next = node;
                    // 因为是环形链表，所以最后一个结点还要指向第一个结点
                    node.next = first;
                    break;
                }
                tempNode = tempNode.next;
            }
        }
        return first;
    }

    /**
     * @Description 3. 打印单向环形链表
     */
    public static void showList(HeroNode first) {
        if (first == null) {
            System.out.println("链表为空！");
            return;
        }
        HeroNode tempNode = first;
        while (true) {
            if (tempNode.next.getNo() == first.getNo()) {
                System.out.println(tempNode);
                break;
            }
            System.out.println(tempNode);
            tempNode = tempNode.next;
        }
    }

}


class HeroNode {
    private int no;             // 本节点数据
    private String name;
    private String nickName;
    public HeroNode next;       // 指向下一个节点

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    public int getNo() {
        return no;
    }

    //为了显示方法,我们重新toString
    @Override
    public String toString() {
        return "HeroNode[no=" + no + ",name=" + name + ",nickname=" + nickName + "]";
    }
}

数组队列栈

luffy博客

Choose mode

链表

链表

# 三、链表

# 1、链表(Linked List)介绍

# 2、单链表的应用实例

# Ⅰ-添加方法一:在添加英雄时，直接添加到链表的尾部

# Ⅱ-添加方法二:根据排名将英雄插入到指定位置

# Ⅲ-修改节点

# Ⅳ-删除节点

# Ⅴ-全部代码

# 3、单链表面试题

# Ⅰ-求单链表中有效节点的个数

# Ⅱ-查找单链表中的倒数第 k 个结点【新浪面试题】

# Ⅲ-单链表的反转【腾讯面试题，有点难度】

# Ⅳ-从尾到头打印单链表

# Ⅴ-合并两个有序的单链表，合并之后的链表依然有序

# 4、双向链表与其实例

# 5、单向与双向链表对比

# 6、单链表之约瑟夫问题

# Ⅰ-问题描述:

# Ⅱ-老师给的思路实现

# Ⅲ-思路改进与代码实现

luffy博客

链表

链表

# 三、链表

# 1、链表(Linked List)介绍

# 2、单链表的应用实例

# Ⅰ-添加方法一:在添加英雄时，直接添加到链表的尾部

# Ⅱ-添加方法二:根据排名将英雄插入到指定位置

# Ⅲ-修改节点

# Ⅳ-删除节点

# Ⅴ-全部代码

# 3、单链表 面试题

# Ⅰ-求单链表中有效节点的个数

# Ⅱ-查找单链表中的倒数第 k 个结点 【新浪面试题】

# Ⅲ-单链表的反转【腾讯面试题，有点难度】

# Ⅳ-从尾到头打印单链表

# Ⅴ-合并两个有序的单链表，合并之后的链表依然有序

# 4、双向链表与其实例

# 5、单向与双向链表对比

# 6、单链表之约瑟夫问题

# Ⅰ-问题描述:

# Ⅱ-老师给的思路实现

# Ⅲ-思路改进与代码实现

# 3、单链表面试题

# Ⅱ-查找单链表中的倒数第 k 个结点【新浪面试题】