一、链表介绍

链表内存中的状态以及小结

QQ截图20200723110033.jpg
QQ截图20200723110040.jpg

二、单链表的应用实例

完整代码：
SingleLinkedListDemo.java

创建节点以及管理链表类

说明：需要创建两个类，一个是节点类，另一个是管理链表的类
① 节点类中需要id、name、sickname以及节点类(用于指向下一个节点)
② 管理链表中的类 首先创建一个头节点(里面没有数据，并且保持不变)，包含方法有：添加方法(插入到链表尾部)，遍历链表。

如下：

  1. //创建管理链表的类
  2. class SingleLinkedList{
  4.     //先初始化一个头节点, 头节点不要动, 不存放具体的数据
  5.     HeroNode head = new HeroNode(0, "", "");
  6.     ...其他等方法    
  7. }
  10. //创建节点
  11. class HeroNode{
  12.     public int id;
  13.     public String name;
  14.     public String nickname;
  15.     public HeroNode next;
  17.     //创建一个构造器，存放id、name、nickname
  18.     public HeroNode(int id, String name, String nickname) {
  19.         super();
  20.         this.id = id;
  21.         this.name = name;
  22.         this.nickname = nickname;
  23.     }
  25.     @Override
  26.     public String toString() {
  27.         return "HeroNode [id=" + id + ", name=" + name + ", nickname=" + nickname + "]";
  28.     }
  31. }

第一种添加方式：添加到链表尾部(包含遍历)

说明：下面是添加节点到链表尾部的方法以及遍历链表的方法。

  1. package LinkedList;
  3. //创建管理链表的类
  4. class SingleLinkedList{
  6.     //先初始化一个头节点, 头节点不要动, 不存放具体的数据
  7.     HeroNode head = new HeroNode(0, "", "");
  9.     //进行添加节点到末尾
  10.     public void addNode(HeroNode node) {
  11.         //首先使用一个临时变量代替head
  12.         HeroNode temp = head;
  13.         //寻找到链表的最底部
  14.         while(true) {
  15.             if(temp.next == null) {
  16.                 break;
  17.             }
  18.             temp = temp.next;
  19.         }
  20.         //插入node节点到最底部
  21.         temp.next = node;
  22.     }
  24.     //遍历链表
  25.     public void showList() {
  26.         //判断链表是否为空
  27.         if(head.next == null) {
  28.             System.out.println("链表为空，无法进行遍历数据！");
  29.             return;
  30.         }
  32.         //使用一个临时变量获取到链表下一个节点
  33.         HeroNode temp = head.next;
  34.         while(true) {
  35.             if(temp == null) {
  36.                 break;
  37.             }
  38.             System.out.println(temp);
  39.             temp = temp.next;
  40.         }
  42.     }
  45. }

进行测试：

  1. package LinkedList;
  3. public class SingleLinkedListDemo {
  4.     public static void main(String[] args) {
  5.         SingleLinkedList list = new SingleLinkedList();
  6.         //创建四个节点
  7.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  8.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  9.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  10.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  12.         //进行添加操作
  13.         list.addNode(node3);
  14.         list.addNode(node1);
  15.         list.addNode(node2);
  16.         //不能进行重复添加相同的节点，可能会发生死循环
  17.         //list.addNode(node3);
  18.         list.addNode(node4);
  20.         //进行遍历链表
  21.         list.showList();
  22.     }
  23. }





运行结果：
QQ截图20200723110915.jpg

第二种添加方式：根据id属性排序添加

QQ截图20200724095127.jpg

说明：addNodeById()是根据id号链式添加的方法，根据id号从小到大进行添加。
① 首先需要一个辅助节点temp也就是进行插入节点位置的前一个节点。
② 每次插入相当于遍历链表，从中找出与id位置相匹配的位置插入，在进行遍历判断过程中，会有三种情况，
第一种是没有找到插入中间位置，插入到尾部，使用temp.next==null判断。
第二种是插入id与原有链表中的id相同，提示无法插入，使用temp.next.id==node.id。
第三种是找到在链表中插入的位置，使用temp.next.id>node.id来判断

插入过程说明：
插入只有两种情况也就是插入到尾部，另一种是插入到链表中，temp代表的插入位置之前的一个节点，那么首先得先将temp的next值赋给node的next也就是node.next = temp.next，
(注意不能直接将node作为temp的next值，这样的话原先temp的next值就会被覆盖从而丢失)
接着将node值赋给temp的next位置，temp.next = node。

flag为true实际代表着链表无法插入id相同的情况，为false代表可以插入，如插入到尾部或者链表中间。

  1. //创建管理链表的类
  2. class SingleLinkedList{
  3.     ...
  4.     public void addNodeById(HeroNode node) {
  5.     //temp就代表待插入节点的前一个节点
  6.     HeroNode temp = head;
  7.     //这个flag代表是否有相同id值，true表示不能插入，false表示能插入
  8.     boolean flag = false;
  9.     while(true) {
  10.         //当temp节点的下一个节点为null，说明在尾部了，跳出循坏在尾部添加
  11.         if(temp.next == null) {
  12.             break;
  13.         }
  14.         //当temp节点下一个节点的id与待插入节点的id相同，flag设置为true，表明不能插入
  15.         if(temp.next.id == node.id) {
  16.             flag = true;
  17.             break;
  18.         }
  19.         //当temp节点下一个节点的id大于待插入节点id，跳出循环，将node节点插入到temp之后
  20.         if(temp.next.id > node.id) {
  21.             break;
  22.         }
  23.         //方便进行遍历
  24.         temp = temp.next;
  25.     }
  27.     if(flag) {
  28.         System.out.println("插入的节点id已存在，无法插入");
  29.     }else {
  30.         //首先插入节点的next先获取到temp的next节点
  31.         node.next = temp.next;
  32.         //再将node节点插入到temp节点之前
  33.         temp.next = node;
  34.     }
  36. }

测试过程：

  1. package LinkedList;
  3. public class SingleLinkedListDemo {
  4.     public static void main(String[] args) {
  5.         SingleLinkedList list = new SingleLinkedList();
  6.         //创建四个节点
  7.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  8.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  9.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  10.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  12.         //进行添加操作
  13.         list.addNodeById(node3);
  14.         list.addNodeById(node2);
  15.         list.addNodeById(node1);
  16.         list.addNodeById(node4);
  17.         list.addNodeById(node1);
  19.         //进行遍历链表
  20.         System.out.println("遍历结果：");
  21.         list.showList();
  22.     }
  23. }

运行结果：
QQ截图20200724100731.jpg

修改节点方法(根据id)

QQ截图20200726100827.jpg

说明：**依旧使用一个辅助节点temp，并且进行遍历修改
① 首先判断是否为空链表，是的话直接退出。
② **在遍历过程中，有两种情况，一种是没有遍历到结尾没有找到修改位置，第二种情况，找到对应id位置进行修改，这里使用flag(true表示能够修改，false表示不能修改)

  1. //创建管理链表的类
  2. class SingleLinkedList{    
  3.     ...
  4.     // 修改节点，根据id编号进行修改
  5.     public void updateNode(HeroNode newnode) {
  6.         // 创建一个辅助节点,令temp为head的next
  7.         HeroNode temp = head.next;
  8.         // 判断是否为空链表情况
  9.         if (temp == null) {
  10.             System.out.println("链表为空，无法进行修改！");
  11.             return;
  12.         }
  13.         // true表示能够修改， false表示不能修改
  14.         boolean flag = false;
  15.         while (true) {
  16.             // 表示到达链表末尾，无法进行插入
  17.             if (temp == null) {
  18.                 break;
  19.             }
  20.             // 找到对应id相同的英雄
  21.             if (temp.id == newnode.id) {
  22.                 flag = true;// 表示能够进行修改
  23.                 break;
  24.             }
  25.             // 进行遍历使用
  26.             temp = temp.next;
  27.         }
  29.         if (flag) {
  30.             temp.name = newnode.name;
  31.             temp.nickname = newnode.nickname;
  32.             System.out.printf("修改id【%d】成功！\n",newnode.id);
  33.         } else {
  34.             System.out.println("链表中无法找到对应id英雄，修改失败！");
  35.         }
  37.     }
  38. }


测试过程：**

  1. package LinkedList;
  3. public class SingleLinkedListDemo {
  4.     public static void main(String[] args) {
  5.         SingleLinkedList list = new SingleLinkedList();
  6.         //创建四个节点
  7.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  8.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  9.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  10.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  12.         //进行添加操作
  13.         list.addNodeById(node3);
  14.         list.addNodeById(node2);
  15.         list.addNodeById(node1);
  16.         list.addNodeById(node4);
  18.         //进行遍历链表
  19.         System.out.println("修改前遍历结果：");
  20.         list.showList();
  22.         //进行修改操作
  23.         list.updateNode(new HeroNode(1, "小丁", "青龙偃月刀"));
  24.         //list.updateNode(new HeroNode(6, "小丁", "青龙偃月刀"));
  25.         System.out.printf("\n修改后遍历结果：\n");
  26.         list.showList();
  28.     }
  29. }

运行结果：
QQ截图20200724103007.jpgQQ截图20200724103044.jpg

删除节点方法

QQ截图20200726100849.jpg
说明：想要删除节点，需要找到删除节点的前一个节点，再进行删除即可。

  1. class SingleLinkedList{    
  2.     ...    
  3.     //根据id来删除节点
  4.     public void delNode(int id) {
  5.         if(head.next == null) {
  6.             System.out.println("链表为空，无法删除!");
  7.             return;
  8.         }
  9.         HeroNode temp = head;
  10.         //true用来表示找到删除的节点，false表示未找到删除的节点
  11.         boolean flag = false;
  12.         while(true) {
  13.             //到链表末尾没有找到对应节点
  14.             if(temp.next == null) {
  15.                 break;
  16.             }
  17.             //找到temp的下一节点为对应删除的节点
  18.             if(temp.next.id == id) {
  19.                 flag = true;
  20.                 break;
  21.             }
  22.             //进行遍历
  23.             temp = temp.next;
  24.         }
  26.         if(flag) {
  27.             temp.next = temp.next.next;
  28.             System.out.printf("成功删除id【%d】",id);
  29.             System.out.println();
  30.         }else {
  31.             System.out.printf("链表中未找到对应id【%d】节点，删除失败!",id);
  32.             System.out.println();
  33.         }
  34.     }
  35. }

测试运行：

  1. package LinkedList;
  3. public class SingleLinkedListDemo {
  4.     public static void main(String[] args) {
  5.         SingleLinkedList list = new SingleLinkedList();
  6.         //创建四个节点
  7.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  8.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  9.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  10.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  12.         //进行添加操作
  13.         list.addNodeById(node3);
  14.         list.addNodeById(node2);
  15.         list.addNodeById(node1);
  16.         list.addNodeById(node4);
  18.         //进行遍历链表
  19.         System.out.println("修改前遍历结果：");
  20.         list.showList();
  22.         //进行删除操作
  23.         list.delNode(5);//删除链表中不存在的情况
  24.         list.delNode(1);//删除链表中的节点情况
  25.         list.delNode(2);
  26.         list.delNode(3);
  27.         list.delNode(4);
  28.         list.delNode(2);//空链表时删除情况
  29.         System.out.printf("\n修改后遍历结果：\n");
  30.         list.showList();
  32.     }
  33. }

运行结果：
QQ截图20200726101146.jpg

三、单链表的常见面试题

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

源代码：SingleLinkedListDemo.java

QQ截图20200727100656.jpg

  1. public class SingleLinkedListDemo {    
  2.     //获取链表中的个数
  3.     public static int getLinedListSize(HeroNode head) {
  4.         //判断链表为空的情况
  5.         if(head.next == null) {
  6.             return 0;
  7.         }
  8.         //使用辅助节点
  9.         int length = 0;
  10.         HeroNode temp = head.next;
  11.         while(temp != null) {
  12.             length++;
  13.             temp = temp.next;
  14.         }
  15.         return length;
  16.     }
  17. }

测试代码：
说明：配合之前单链表的应用来进行测试

  1. public class SingleLinkedListDemo {
  2.     public static void main(String[] args) {
  3.         SingleLinkedList list = new SingleLinkedList();
  4.         //创建四个节点
  5.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  6.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  7.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  8.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  10.         //进行添加操作
  11.         list.addNodeById(node3);
  12.         list.addNodeById(node2);
  13.         list.addNodeById(node1);
  14.         list.addNodeById(node4);
  16.         //获取链表中的个数
  17.         int size = SingleLinkedListDemo.getLinedListSize(list.head);
  18.         System.out.printf("链表中的节点有%d个。\n",size);
  20.     }
  21. }

运行结果：
QQ截图20200727100913.jpg

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

源代码：SingleLinkedListDemo.java

QQ截图20200727102513.jpg

  1. public class SingleLinkedListDemo {    
  2.     //获取链表的倒数第k个节点
  3.     public static HeroNode getLastIndexNode(HeroNode head,int k) {
  4.         //判断链表为空的情况
  5.         if(head.next == null) {
  6.             return null;
  7.         }
  8.         //获取链表中的个数
  9.         int size = SingleLinkedListDemo.getLinedListSize(head);
  10.         //对于k的取值进行判断，若位置不合理返回null
  11.         if(k<=0 || k>size) {
  12.             return null;
  13.         }
  14.         //合理情况下求链表中的第size-k个节点
  15.         //使用一个辅助节点
  16.         HeroNode temp = head.next;
  17.         for(int i=1;i<=size-k;i++) {
  18.             temp = temp.next;
  19.         }
  21.         return temp;
  22.     }
  23. }

测试代码：

  1. package LinkedList;
  3. public class SingleLinkedListDemo {
  4.     public static void main(String[] args) {
  5.         SingleLinkedList list = new SingleLinkedList();
  6.         //创建四个节点
  7.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  8.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  9.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  10.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  12.         //进行添加操作 这里是按照id进行添加的
  13.         list.addNodeById(node3);
  14.         list.addNodeById(node2);
  15.         list.addNodeById(node1);
  16.         list.addNodeById(node4);
  18.         //获取链表中的个数
  19.         int size = SingleLinkedListDemo.getLinedListSize(list.head);
  20.         System.out.printf("链表中的节点有%d个。\n",size);
  22.         //进行遍历链表
  23.         System.out.println("进行遍历链表：");
  24.         list.showList();
  25.         System.out.println();
  27.         //获取链表的倒数第4个节点
  28.         HeroNode node = SingleLinkedListDemo.getLastIndexNode(list.head, 4);
  29.         System.out.println("倒数第一个节点为："+node);
  31.     }
  32. }

运行结果：
QQ截图20200727101634.jpg

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

源代码：SingleLinkedListDemo.java

QQ截图20200727125100.jpg

思路说明：
QQ截图20200727125636.jpg

  1. public class SingleLinkedListDemo {
  2.     //反转链表
  3.     public static void reverseList(HeroNode head) {
  4.         //当链表为空或1个节点时不进行反转
  5.         if(head.next == null || head.next.next == null) {
  6.             System.out.println("当前链表为空或有一个元素，无法反转！");
  7.             return;
  8.         }
  10.         //设置其为当前指向节点
  11.         HeroNode curNode = head.next;
  12.         //设置其为当前指向节点的后一节点
  13.         HeroNode nextNode = null;
  14.         //设置一个反转的链表,用于存放之后遍历的链表
  15.         HeroNode reversehead = new HeroNode(0, "", "");
  16.         while(curNode!=null) {
  17.             nextNode = curNode.next;//用于获取到当前节点cur后一个节点
  18.             curNode.next = reversehead.next;//这段代码相当于将每次获取的节点从后往前存放
  19.             reversehead.next = curNode;//用于保存存入到reverse后的节点
  20.             curNode = nextNode;//让curNode获取到nextNode的值，就像向后遍历一样
  21.         }
  22.         head.next = reversehead.next;//将反转过后的链表接连到初始链表head上
  23.         System.out.println("链表反转成功");
  24.         System.out.println();
  26.     }
  27. }

测试代码：

  1. package LinkedList;
  3. public class SingleLinkedListDemo {
  4.     public static void main(String[] args) {
  5.         SingleLinkedList list = new SingleLinkedList();
  6.         //创建四个节点
  7.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  8.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  9.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  10.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  12.         //进行添加操作 这里是按照id进行添加的
  13.         list.addNodeById(node3);
  14.         list.addNodeById(node2);
  15.         list.addNodeById(node1);
  16.         list.addNodeById(node4);
  18.         //进行遍历链表
  19.         System.out.println("进行遍历链表：");
  20.         list.showList();
  21.         System.out.println();
  23.         //链表进行反转操作
  24.         reverseList(list.head);
  25.         System.out.println("链表反转之后：");
  26.         list.showList();
  28.     }
  29. }

运行结果：
QQ截图20200727125826.jpg

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

源代码：SingleLinkedListDemo.java

思路分析：
QQ截图20200728102411.jpg

这里演示方式2：使用栈进行存储再打印

  1. package LinkedList;
  3. import java.util.Stack;
  5. public class SingleLinkedListDemo {    
  6.     //将链表从后往前打印
  7.     //使用到栈
  8.     public static void reversedPrint(HeroNode head) {
  9.         //判断链表是否为空
  10.         if(head.next == null) {
  11.             System.out.println("链表为空，无法打印");
  12.             return;
  13.         }
  15.         //设置一个辅助节点
  16.         HeroNode cur = head.next;
  17.         //使用栈的api
  18.         Stack<HeroNode> stack = new Stack<HeroNode>();
  19.         while(cur != null) {
  20.             stack.add(cur);
  21.             //链表不断向后遍历，并压入栈
  22.             cur = cur.next;
  23.         }
  24.         //进行遍历栈
  25.         while(stack.size()>0) {
  26.             System.out.println(stack.pop());
  27.         }
  29.     }
  30. }

测试过程：

说明：在遍历链表过程中不断存入栈中，最后再遍历栈中的数据，这样能够使链表的结构不变化**

  1. package LinkedList;
  3. import java.util.Stack;
  5. public class SingleLinkedListDemo {
  6.     public static void main(String[] args) {
  7.         SingleLinkedList list = new SingleLinkedList();
  8.         //创建四个节点
  9.         HeroNode node1 = new HeroNode(1, "丁明", "青龙偃妈刀");
  10.         HeroNode node2 = new HeroNode(2, "小殷", "优雅男神");
  11.         HeroNode node3 = new HeroNode(3, "单泽鹏", "马尾小萝莉");
  12.         HeroNode node4 = new HeroNode(4, "顾天乐", "金刚小铁拳");
  14.         //进行添加操作 这里是按照id进行添加的
  15.         list.addNode(node3);
  16.         list.addNode(node2);
  17.         list.addNode(node1);
  18.         list.addNode(node4);
  20.         //进行遍历链表
  21.         System.out.println("进行遍历链表：");
  22.         list.showList();
  23.         System.out.println();
  25.         //将链表从后往前打印输出
  26.         System.out.println("链表从后往前打印：");
  27.         SingleLinkedListDemo.reversedPrint(list.head);
  29.     }
  30. }

运行结果：
QQ截图20200728102353.jpg

四、双向链表的应用实例

源代码：DoubleLinkedListDemo.java
**

思路分析(双向链表与单链表的不同)

QQ截图20200728104339.jpg

代码实现

说明：此次代码实现了增加节点(顺序)、增加节点(按照id小到大)、删除节点、更改节点、遍历链表、获取头节点。

有无变化说明
对于遍历节点、修改节点对于单链表都没有变化。
有变化的说明：
① 增加节点(顺序)：需要给新增节点的pre赋值
② 增加节点(按照id)：由单链表给两个next赋值改变为两个pre以及两个next，并且对于temp.next.pre这个节点的pre在链表最后位置添加时要注意空指针的情况，所以要加上判断。
③ 删除节点：单链表需要查找删除节点的前一个节点，而双链表可以直接查找到对应节点利用pre进行删除节点，对于获取到temp.next.pre也要进行null值判断进行赋值。

  1. package LinkedList;
  3. public class DoubleLinkedListDemo {
  5.     public static void main(String[] args) {
  6.         DoubleLinkedList list = new DoubleLinkedList();
  8.         //创建四个节点
  9.         HeroNode2 node1 = new HeroNode2(1, "丁明", "青龙偃妈刀");
  10.         HeroNode2 node2 = new HeroNode2(2, "小殷", "优雅男神");
  11.         HeroNode2 node3 = new HeroNode2(3, "单泽鹏", "马尾小萝莉");
  12.         HeroNode2 node4 = new HeroNode2(4, "顾天乐", "金刚小铁拳");
  14.         //进行添加操作 这里是按照id进行添加的
  15.         list.addNode(node1);
  16.         list.addNode(node2);
  17.         list.addNode(node3);
  18.         list.addNode(node4);
  20.         System.out.println("进行修改操作：");
  21.         HeroNode2 node5 = new HeroNode2(3, "长路", "无敌拳霸");
  22.         list.updateNode(node5);
  23.         //进行遍历操作
  24.         list.showList();
  26.         System.out.println();
  27.         System.out.println("进行删除操作：");
  28.         list.delNode(4);
  29.         list.showList();
  31.         System.out.println();
  32.         System.out.println("进行插入(根据id)操作：");
  33.         list.addNodeById(new HeroNode2(0, "林儿", "长路对象"));
  34.         list.showList();
  36.     }
  38. }
  40. //创建管理链表的类
  41. class DoubleLinkedList{
  43.     //先初始化一个头节点, 头节点不要动, 不存放具体的数据
  44.     public HeroNode2 head = new HeroNode2(0, "", "");
  46.     //返回头节点
  47.     public HeroNode2 getHeadNode() {
  48.         return head;
  49.     }
  51.     //进行添加节点到末尾
  52.     public void addNode(HeroNode2 node) {
  53.         //首先使用一个临时变量代替head
  54.         HeroNode2 temp = head;
  55.         //寻找到链表的最底部
  56.         while(true) {
  57.             if(temp.next == null) {
  58.                 break;
  59.             }
  60.             temp = temp.next;
  61.         }
  62.         //插入node节点到最底部
  63.         temp.next = node;
  64.         //增加点：将最后添加的节点的pre得到temp节点
  65.         node.pre = temp;
  66.     }
  68.     //插入节点按照id编号排序进行插入
  69.     public void addNodeById(HeroNode2 node) {
  70.         //temp就代表待插入节点的前一个节点
  71.         HeroNode2 temp = head;
  72.         //这个flag代表是否有相同id值，true表示不能插入，false表示能插入
  73.         boolean flag = false;
  74.         while(true) {
  75.             //当temp节点的下一个节点为null，说明在尾部了，跳出循坏在尾部添加
  76.             if(temp.next == null) {
  77.                 break;
  78.             }
  79.             //当temp节点下一个节点的id与待插入节点的id相同，flag设置为true，表明不能插入
  80.             if(temp.next.id == node.id) {
  81.                 flag = true;
  82.                 break;
  83.             }
  84.             //当temp节点下一个节点的id大于待插入节点id，跳出循环，将node节点插入到temp之后
  85.             if(temp.next.id > node.id) {
  86.                 break;
  87.             }
  88.             //方便进行遍历
  89.             temp = temp.next;
  90.         }
  92.         if(flag) {
  93.             System.out.printf("插入的节点id【%d】已存在，无法插入\n",node.id);
  94.         }else {
  95.             if(temp.next != null) {
  96.                 //若不是最后一个节点，那么就可以获取到temp.next并赋值
  97.                 temp.next.pre = node;
  98.             }
  99.             //首先插入节点的next先获取到temp的next节点
  100.             node.next = temp.next;
  101.             //插入的节点的前一个节点为temp
  102.             node.pre = temp;
  103.             //再将node节点插入到temp节点之前
  104.             temp.next = node;
  105.         }
  107.     }
  109.     //遍历链表
  110.     public void showList() {
  111.         //判断链表是否为空
  112.         if(head.next == null) {
  113.             System.out.println("链表为空，无法进行遍历数据！");
  114.             return;
  115.         }
  117.         //使用一个临时变量获取到链表下一个节点
  118.         HeroNode2 temp = head.next;
  119.         while(true) {
  120.             if(temp == null) {
  121.                 break;
  122.             }
  123.             System.out.println(temp);
  124.             temp = temp.next;
  125.         }
  127.     }
  129.     // 修改节点，根据id编号进行修改
  130.     public void updateNode(HeroNode2 newnode) {
  131.         // 创建一个辅助节点,令temp为head的next
  132.         HeroNode2 temp = head.next;
  133.         // 判断是否为空链表情况
  134.         if (temp == null) {
  135.             System.out.println("链表为空，无法进行修改！");
  136.             return;
  137.         }
  138.         // true表示能够修改， false表示不能修改
  139.         boolean flag = false;
  140.         while (true) {
  141.             // 表示到达链表末尾，无法进行插入
  142.             if (temp == null) {
  143.                 break;
  144.             }
  145.             // 找到对应id相同的英雄
  146.             if (temp.id == newnode.id) {
  147.                 flag = true;// 表示能够进行修改
  148.                 break;
  149.             }
  150.             // 进行遍历使用
  151.             temp = temp.next;
  152.         }
  154.         if (flag) {
  155.             temp.name = newnode.name;
  156.             temp.nickname = newnode.nickname;
  157.             System.out.printf("修改id【%d】成功！\n",newnode.id);
  158.         } else {
  159.             System.out.println("链表中无法找到对应id英雄，修改失败！");
  160.         }
  162.     }
  164.     //根据id来删除节点 由于是双向链表就可以查找对应要删除的节点即可进行删除
  165.     public void delNode(int id) {
  166.         if(head.next == null) {
  167.             System.out.println("链表为空，无法删除!");
  168.             return;
  169.         }
  170.         //直接获取到头节点的下一个节点
  171.         HeroNode2 temp = head.next;
  172.         //true用来表示找到删除的节点，false表示未找到删除的节点
  173.         boolean flag = false;
  174.         while(true) {
  175.             //到链表末尾没有找到对应节点
  176.             if(temp == null) {
  177.                 break;
  178.             }
  179.             //找到temp的下一节点为对应删除的节点
  180.             if(temp.id == id) {
  181.                 flag = true;
  182.                 break;
  183.             }
  184.             //进行遍历
  185.             temp = temp.next;
  186.         }
  188.         if(flag) {
  189.             //删除节点的前一个节点的next为下一个节点
  190.             temp.pre.next = temp.next;
  191.             //为删除节点的后一个节点的pre赋值
  192.             //避免删除项是最后一个节点的情况
  193.             if(temp.next != null) {
  194.                 temp.next.pre = temp.pre;
  195.             }
  196.             System.out.printf("成功删除id【%d】",id);
  197.             System.out.println();
  198.         }else {
  199.             System.out.printf("链表中未找到对应id【%d】节点，删除失败!",id);
  200.             System.out.println();
  201.         }
  202.     }
  204. }
  206. //创建节点
  207. class HeroNode2{
  208.     public int id;
  209.     public String name;
  210.     public String nickname;
  211.     public HeroNode2 next;//指向后面一个节点
  212.     public HeroNode2 pre;//指向前面一个节点
  214.     //创建一个构造器，存放id、name、nickname
  215.     public HeroNode2(int id, String name, String nickname) {
  216.         super();
  217.         this.id = id;
  218.         this.name = name;
  219.         this.nickname = nickname;
  220.     }
  222.     @Override
  223.     public String toString() {
  224.         return "HeroNode2 [id=" + id + ", name=" + name + ", nickname=" + nickname + "]";
  225.     }
  226. }

运行结果：
QQ截图20200805155009.jpg

五、单向环形链表

1. 单向环形链表应用场景

QQ截图20200805160804.jpg

2. 单向环形链表介绍

源代码：Josepfo.java

示意图：
QQ截图20200805160846.jpg

① Josephu 问题

问题描述：
QQ截图20200805160943.jpgQQ截图20200805160952.jpg

② 构建约瑟夫环以及遍历约瑟夫环(代码实现)

QQ截图20200805165622.jpg

创建约瑟夫环的节点以及约瑟夫环对象

  1. //表示约瑟夫环
  2. class CircleSingleLinkedList{
  4.     //需要创建第一个节点
  5.     private Boy first = null;
  7. }
  9. class Boy{
  10.     private Integer id;
  11.     private Boy next;
  13.     public Boy(Integer id) {
  14.         super();
  15.         this.id = id;
  16.     }
  18.     public Integer getId() {
  19.         return id;
  20.     }
  22.     public void setId(Integer id) {
  23.         this.id = id;
  24.     }
  26.     public Boy getNext() {
  27.         return next;
  28.     }
  30.     public void setNext(Boy next) {
  31.         this.next = next;
  32.     }
  34. }

创建约瑟夫环


说明：对于插入有两种情况，第一种是插入第一个节点时，第二种就是插入第二个节点之后所有节点。
需要的节点：**每次插入时创建的节点以及辅助节点(用于指向新创建的节点位置，不对first节点进行更改)。

  1. //表示约瑟夫环
  2. class CircleSingleLinkedList{
  4.     //需要创建第一个节点
  5.     private Boy first = null;
  7.     public void createJosepho(int num) {
  8.         //对创建个数进行规范
  9.         if(num<1) {
  10.             System.out.println("创建人数过少，请重新创建！");
  11.             return;
  12.         }
  13.         //创建一个辅助节点
  14.         Boy curBoy = null;
  16.         //进行循环插入
  17.         for(int i=1;i<=num;i++) {
  18.             Boy boy = new Boy(i);
  19.             //如果是第一个创建的
  20.             if(i == 1) {
  21.                 first = boy;
  22.                 first.setNext(first);
  23.                 //辅助节点获取到新插入的节点
  24.                 curBoy = first;
  25.             }else {
  26.                 //不是第一次插入时根据辅助节点插入
  27.                 curBoy.setNext(boy);
  28.                 boy.setNext(first);
  29.                 curBoy = boy;
  30.             }
  31.         }
  32.         System.out.printf("%d人的约瑟夫环创建成功\n",num);
  33.     }
  34. }

遍历约瑟夫环


说明：**需要判断链表是否为空以及使用辅助节点来进行遍历，遍历时的条件是当前节点的下一个节点为first第一个节点时遍历结束。

  1.     //进行遍历约瑟夫环
  2.     public void showJosepho() {
  3.         //判断是否为空
  4.         if(first == null) {
  5.             System.out.println("约瑟夫环为空，无法遍历！");
  6.             return;
  7.         }
  8.         //使用辅助节点来进行遍历
  9.         Boy curBoy = first;
  11.         while(true) {
  12.             System.out.println("id："+ curBoy.getId());
  13.             if(curBoy.getNext() == first) {
  14.                 break;
  15.             }
  16.             curBoy = curBoy.getNext();
  17.         }
  18.     }

测试创建与遍历

  1. package LinkedList;
  3. public class Josepfo {
  5.     public static void main(String[] args) {
  6.         //创建数量为5的约瑟夫环
  7.         CircleSingleLinkedList list = new CircleSingleLinkedList();
  8.         list.createJosepho(5);
  9.         list.showJosepho();
  10.     }
  12. }

运行结果：
QQ截图20200805170723.jpg

③ 小孩出圈(传入初始位置、数数数量、总人数)

QQ截图20200806104607.jpg

说明：接连在上面方法的类中，由于是单向链表，所以我们在出圈过程中还应该知晓出圈节点的前一个节点
① **初步状态辅助节点在整个环形链表最后。
② 根据初始位置来调整helper、first节点位置，始终一前一后状态。
③ 来根据数数进行出圈报出id名。**

  1.     public void countBoy(int startNo,int countNum,int nums) {
  2.         //如果链表为空，初始位置小于1，初始位置大于总数
  3.         if(startNo<1 || startNo>nums || first == null) {
  4.             System.out.println("您输入的参数有误，请重新输入！");
  5.         }
  7.         //定义一个辅助节点
  8.         Boy helper = first;
  9.         //将辅助节点变为最后一个节点来紧跟first头节点
  10.         while(true) {
  11.             if(helper.getNext() == first) {
  12.                 break;
  13.             }
  14.             helper = helper.getNext();
  15.         }
  17.         //根据初始位置进行调位
  18.         for(int i = 0;i<startNo-1;i++) {
  19.             //两个节点一起移动
  20.             first = first.getNext();
  21.             helper = helper.getNext();
  22.         }
  24.         while(true) {
  25.             //如果环中只有一个节点了，那么退出循环
  26.             if(helper == first) {
  27.                 break;
  28.             }
  30.             //进行数数
  31.             for(int i=0;i<countNum-1;i++) {
  32.                 first = first.getNext();
  33.                 helper = helper.getNext();
  34.             }
  36.             //将first指定的移除  
  37.             System.out.println("移除的id为："+first.getId());
  38.             first = first.getNext();//这里first移到移除人的后方
  39.             helper.setNext(first);//辅助节点的next值指向新的first
  41.         }
  42.         System.out.println("最后一位id为："+first.getId());
  45.     }

测试代码：

  1. package LinkedList;
  3. public class Josepfo {
  5.     public static void main(String[] args) {
  6.         //创建数量为5的约瑟夫环
  7.         CircleSingleLinkedList list = new CircleSingleLinkedList();
  8.         list.createJosepho(5);
  9.         list.showJosepho();
  11.         //起始位置为1，报数为2，总人数为5
  12.         System.out.printf("\n开始数数了:\n");
  13.         list.countBoy(1, 2, 5);
  14.     }
  15. }

运行结果：
QQ截图20200806105003.jpg

整理者：长路 时间：?-2020/8/6