一、单向链表

1、基本介绍

  1. 链表是有序的列表，但是他再内存中的存储如下 —————->
  2. 链表是以节点的方式来存储数据的，是链式存储
  3. 每个节点包含data域（存数据） next域（存下一个节点的地址）
  4. 链表中各个节点不一定是连续存储。（可以充分利用碎片内存）
  5. 链表分为 带头节点链表 和 不带头节点链表，根据实际需求来确定

未命名图片.png

2、带头节点的链表

未命名图片.png

  1. head节点不存放任何具体数据，作用就是表示单链表的头。
  2. 最后一个节点的next域 存放的是null，表示这是尾部
  3. 从单项链表中添加一个节点的思路
    • 直接在添加时添加到链表的尾部
      • 首先判断链表是否为空 head.next == null
      • 创建一个temp辅助变量，temp = head
      • 遍历时 如果当 temp.next = null, 说明跳出循环，进行添加 temp.next = 新节点
      • 每循环一次，temp向后移动一位
    • 根据id的大小，按顺序添加到链表中
      • 首先判断是否链表是否为空
      • 需要一个temp辅助变量 temp = head
      • 首先需要搞清楚，如果 现在链表中有 1 3 两个节点，你需要将2 添加进去
      • 在循环中 如果 **te**``**mp.next.id > 新节点.id ** 则表示可以将节点插入到 temp 和 temp.next 之间，break;退出循环
      • 使用一个辅助变量 flag ，表示id是重复，就给赋值上true
      • 在循环中，如果**temp.next.id == 新节点.id** 则表示id重复，不能进行插入 falg = true
      • 每循环一次，temp向后移动一位
      • 判断如果为false 就给插入 **//2.next = 1.next; 1.next = 2;** 这样 2 就被插入到 1 和 3的中间了
      • 如果是true 给出提示信息，表示id重复

未命名图片.png

  1. 根据id更新一个节点的数据，不更新 id 和 next ，其余都可以更新 的思路
    • 先遍历 (遍历前先判断链表是否为空)
    • 在循环中 判断 if（temp.next.id == 新节点.id) 找到了就退出循环
    • 没循环一次 temp就往后移动一位
    • 可以使用一个flag变量 来根据变量判断 是否找到了 如果为true则更新 为false表示没找到
  2. 删除节点思路
    • 我们先找到需要删除的这个节点的 前面一个节点 temp
    • 然后 temp.next = temp.next.next 这样就删除了中间的那个节点
    • 举例：1 2 3 个节点，1的下一个节点是 1.next.next 则 1.next = 3 ，这样2 就没了
    • 被删除的节点没有了其他引用的指向，会被垃圾回收器机制回收

未命名图片.png

二、单项链表代码实现

  1. package com.yixuexi.linkedList;
  3. import java.util.Stack;
  5. /**
  6.  * 2020/10/10   20:10
  7.  */
  8. //模拟带头节点的单向链表
  9. public class HeadLinkedListDemo {
  10.     public static void main(String[] args) {
  11.         //进行测试
  12.         //首先创建几个人物数据
  13.         HeroNode n1 = new HeroNode(1,"松江","及时雨");
  14.         HeroNode n2 = new HeroNode(2,"李逵","黑旋风");
  15.         HeroNode n3 = new HeroNode(3,"吴用","智多星");
  16.         HeroNode n4 = new HeroNode(4,"卢俊义","玉麒麟");
  17.         HeroNode n5 = new HeroNode(5,"武大郎","烧饼哥");
  19.         //创建一个链表
  20.         HeadLinkedList headLinkedList = new HeadLinkedList();
  22.         //往链表中添加数据
  23.         headLinkedList.add(n1);
  24.         headLinkedList.add(n2);
  25.         headLinkedList.add(n5);
  27.         //查看链表中的数据
  28.         headLinkedList.list();
  30.         //往链表中添加数据
  31.         headLinkedList.addByOrder(n3);
  32.         headLinkedList.addByOrder(n4);
  33.         headLinkedList.addByOrder(n4);
  35.         //分割线
  36.         System.out.println("------------------------------------------------->");
  38.         //再次查看链表中的数据
  39.         headLinkedList.list();
  41.         //分割线
  42.         System.out.println("------------------------------------------------->");
  44.         //更新链表中的数据
  45.         HeroNode newn5 = new HeroNode(5,"武松","打虎哥");
  46.         HeroNode newn6 = new HeroNode(6,"武松","打虎哥");
  48.         headLinkedList.update(newn5);
  49.         headLinkedList.update(newn6);
  51.         //再次查看链表中的数据
  52.         headLinkedList.list();
  54.         //分割线
  55.         System.out.println("------------------------------------------------->");
  57.         //删除链表中的数据
  58.         headLinkedList.delete(2);
  59.         //查看删除之后的数据
  60.         headLinkedList.list();
  62.         //查看链表中有效数据的个数
  63.         System.out.println(HeadLinkedList.getLength(headLinkedList.getHead()));
  65.         //查看链表中倒数第2个节点
  66.         HeroNode last = HeadLinkedList.getLast(headLinkedList.getHead(), 2);
  67.         System.out.println(last);
  69.         //分割线
  70.         System.out.println("------------------------------------------------->");
  71.         //反转链表
  72.         //HeadLinkedList.reverse(headLinkedList.getHead());
  73.         //headLinkedList.list();
  75.         //分割线
  76.         System.out.println("------------------------------------------------->");
  77.         // 反向打印链表
  78.         HeadLinkedList.reversePrint(headLinkedList.getHead());
  79.     }
  80. }
  81. //创建一个单向链表类，用来管理单项链表
  82. class HeadLinkedList {
  85.     //在这个单项链表类中有一个 头节点，这个头节点不能动
  86.     private HeroNode head = new HeroNode(0, "", "");
  88.     public HeroNode getHead() {
  89.         return head;
  90.     }
  92.     /**
  93.      * 此方法 添加数据的时候没有顺序，是按照先添加的在前面，后添加的在后面的顺序
  94.      *
  95.      * @param heroNode
  96.      */
  97.     public void add(HeroNode heroNode) {
  98.         //由于每次添加节点都是往链表的最后去添加，所以先要遍历一遍链表，找出最后那个元素
  99.         //这里遍历我们使用一个 temp临时变量 辅助我们遍历
  100.         //这里这个temp就是头节点，使用循环，如果temp.next == null，则表示它是最后一个节点
  101.         //如果 temp.next != null 则表示它不是最后一个节点，则往后移一位， temp = temp.next;
  102.         HeroNode temp = head;
  103.         while (true) {
  104.             if (temp.next == null) {
  105.                 //说明此时 temp是最后一个节点 直接跳出循环
  106.                 break;
  107.             }
  108.             //能执行到这里，则表示不是最后一个节点，往后移动一位，继续循环
  109.             temp = temp.next;
  110.         }
  111.         //执行到这里，说明此时的temp一定为最后一个节点，直接将节点添加到 temp.next 即可
  112.         temp.next = heroNode;
  113.     }
  115.     /**
  116.      * 按照id的顺序进行添加
  117.      * 添加的时候按照数据 的id 进行排序，id 为 1 的在空节点后面 1 ->> 2 ->> 3 ->> 4
  118.      */
  119.     public void addByOrder(HeroNode heroNode) {
  120.         //假设：现在链表中的数据为  1  3  4
  121.         //现在 需要将2 插入到 1 和 3 的中间去
  122.         //因为头节点不能动，所以需要一个temp辅助变量 来帮助我们遍历
  123.         HeroNode temp = head;
  124.         //需要使用一个flag辅助我们 判断是否插入的数据id已经存在了
  125.         Boolean flag = false;
  126.         //首先判断，如果这个链表为空，则直接添加在链表的后面即可
  127.         if (temp.next == null) {
  128.             temp.next = heroNode;
  129.             return;
  130.         }
  131.         //循环 找到插入数据的位置  假设 将 2 插入到 1 3 中间
  132.         // 则 2.next = 1.next;  1.next = 2;  这样 2 就被插入到 1 和 3的中间了
  133.         while (true) {
  134.             //这样则表示需要插入的位置找到了，就在 temp 和 temp.next 的中间
  135.             if (temp.next.id > heroNode.id) {
  136.                 break;
  137.             } else if (temp.next.id == heroNode.id) { //表示插入的数据id在链表中已经存在了
  138.                 flag = true;
  139.                 break;
  140.             }
  141.             //如果上面都没有实现则 temp向后移动一位
  142.             temp = temp.next;
  144.         }
  145.         // 将节点插入到指定位置 temp 和 temp.next之间
  146.         if (flag) {
  147.             System.out.println("你要添加节点的id已经存在 id = " + heroNode.id + " 无法添加");
  148.         } else {
  149.             // 则 2.next = 1.next;  1.next = 2;  这样 2 就被插入到 1 和 3的中间了
  150.             heroNode.next = temp.next;
  151.             temp.next = heroNode;
  152.         }
  153.     }
  155.     /**
  156.      * 根据id 对节点的姓名和绰号进行更新
  157.      *
  158.      * @param newHeroNode
  159.      */
  160.     public void update(HeroNode newHeroNode) {
  161.         //需要使用一个辅助变量 temp
  162.         HeroNode temp = head;
  163.         //首先判断是否为空，如果为空直接退出
  164.         if (temp.next == null) {
  165.             System.out.println("链表为空，请加入节点后在进行更新！");
  166.             return;
  167.         }
  168.         //使用循环找出id为 newHeroNode.id 的节点
  169.         Boolean flag = false;
  170.         while (true) {
  171.             if (temp == null) {
  172.                 break;
  173.             }
  174.             //如果找到了 那么直接跳出循环，因为当前temp 就是需要修改的节点
  175.             if (temp.id == newHeroNode.id) {
  176.                 flag = true;
  177.                 break;
  178.             }
  179.             //没有找到则向后移动一位
  180.             temp = temp.next;
  181.         }
  182.         //判断 如果flag为true 则表示当前temp是需要修改的
  183.         if (flag) {
  184.             temp.name = newHeroNode.name;
  185.             temp.nickname = newHeroNode.nickname;
  187.         } else {
  188.             System.out.println("没有找到对应id的节点，请输入正确的数据");
  189.         }
  190.     }
  192.     //删除节点
  193.     public void delete(int id) {
  194.         //辅助变量
  195.         HeroNode temp = head;
  196.         // 标记
  197.         boolean flag = false;
  198.         //思路：找到要删除的节点的前面那个 节点  temp
  199.         //然后 temp.next = temp.next.next  这样中间那个节点的指向就没了，垃圾回收器就回收了
  200.         while (true) {
  201.             if (temp.next == null) {
  202.                 return;
  203.             }
  204.             if (temp.next.id == id) {
  205.                 flag = true;
  206.                 break;
  207.             }
  208.             // 如果都没有 则向后移动一位
  209.             temp = temp.next;
  210.         }
  212.         if (flag) {
  213.             temp.next = temp.next.next;
  214.         } else {
  215.             System.out.println("没有找到对应的节点id ： " + id);
  216.         }
  217.     }
  219.     //用来展示链表中的数据
  220.     public void list() {
  221.         //使用一个temp辅助变量来帮助我们进行循环遍历
  222.         HeroNode temp = head;
  223.         //首先判断一下这个链表是否为空链表
  224.         //如果头节点的next域 为空则表示没有下一个节点，为空链表
  225.         if (temp.next == null) {
  226.             return;
  227.         }
  228.         // 因为上面做了判断了，所以直接输出就行
  229.         //然后把temp往后移动一位，如果temp.next为空，则表示到头了
  230.         while (true) {
  231.             System.out.println(temp.next);
  232.             temp = temp.next;
  233.             if (temp.next == null) {
  234.                 break;
  235.             }
  236.         }
  237.     }
  239.     //用来查看链表中有效数据的个数
  240.     //传过来一个头节点，即可得到他的长度
  241.     public static int getLength(HeroNode head){
  242.         //判断如果这个链表是空链表的话 直接return 0 就行
  243.         if (head.next == null){
  244.             return 0;
  245.         }
  246.         //因为不算上 头节点，所以是 head.next
  247.         HeroNode temp = head.next;
  248.         int length = 0;
  249.         while ( temp != null){
  250.             length ++;
  251.             temp = temp.next;
  252.         }
  253.         return length;
  254.     }
  256.     //用来查看链表中倒数第K个节点
  257.     public static HeroNode getLast(HeroNode head, int index){
  258.         //1.首先根据头节点 得到链表的长度
  259.         //判断如果这个链表是空链表的话 直接return 0 就行
  260.         if (head.next == null){
  261.             return null;
  262.         }
  263.         //因为不算上 头节点，所以是 head.next
  264.         HeroNode temp = head.next;
  265.         int length = 0;
  266.         while ( temp != null){
  267.             length ++;
  268.             temp = temp.next;
  269.         }
  270.         //2. 做一个数据的校验，判断index是否合理
  271.         if(index <= 0 || index > length){
  272.             return null;
  273.         }
  274.         //3. 进行遍历，倒数第几个 ： 长度 - 倒数第几个 = 要找的那个
  275.         HeroNode temp2 = head;  //辅助变量，帮我们遍历
  276.         for(int i = 0; i <= length - index; i++){
  277.             if (temp2.next == null){
  278.                 break;
  279.             }
  280.             temp2 = temp2.next;
  281.         }
  282.         return temp2;
  283.     }
  285.     //传入一个头节点，对其进行链表反转
  286.     public static void reverse(HeroNode head){
  287.         //如果链表为空 或者 链表中就一个元素，那么直接返回这个链表就行，不用反转
  288.         if (head.next == null || head.next.next == null){
  289.             return;
  290.         }
  291.         //定义一个辅助变量，帮助我们遍历链表
  292.         HeroNode cur = head.next;
  293.         //此变量永远指向 cur的下一个节点
  294.         HeroNode next = null;
  295.         //新的头节点
  296.         HeroNode reverseHead = new HeroNode(0,"","");
  297.         while (cur != null){
  298.             //保存cur的下一个节点，防止丢失
  299.             next = cur.next;
  300.             //将cur的下一个节点指向新的链表的最前端 右边的那条链子
  301.             cur.next = reverseHead.next;
  302.             //头插法，将每一个遍历的节点插入到链表的最前端  左边的那条链子
  303.             reverseHead.next = cur;
  304.             //向后移动一位
  305.             cur = next;
  306.         }
  307.         //将head.next 执行reverserHead.next 实现单链表的反转
  308.         head.next = reverseHead.next;
  310.     }
  312.     //从头到尾打印单链表，使用栈数据结构
  313.     public static void reversePrint(HeroNode head){
  314.         //先判断 链表是否为空。
  315.         if(head.next == null){
  316.             return;
  317.         }
  318.         Stack<HeroNode> stack = new Stack<>();
  319.         HeroNode temp = head.next;
  320.         while (temp != null){
  321.             //把节点压入栈中【先进后出】
  322.             stack.push(temp);
  323.             //向后移动一位
  324.             temp = temp.next;
  326.         }
  327.         //将栈中的节点进行打印,因为是先进后出，所以就完成了倒序打印
  328.         while (stack.size() > 0){
  329.             System.out.println(stack.pop());
  330.         }
  331.     }
  332. }
  333. //创建一个节点类
  334. class HeroNode{
  335.     public int id;
  336.     public String name;
  337.     public String nickname;
  338.     public HeroNode next;  //表示单向链表中的next区域，存放下一个节点
  339.     //构造器，
  340.     public HeroNode(int id, String name, String nickname) {
  341.         this.id = id;
  342.         this.name = name;
  343.         this.nickname = nickname;
  344.     }
  345.     //重写toString的时候 next不需要重写
  346.     @Override
  347.     public String toString() {
  348.         return "HeroNode{" +
  349.                 "id=" + id +
  350.                 ", name='" + name + '\'' +
  351.                 ", nickname='" + nickname + '\'' +
  352.                 '}';
  353.     }
  354. }

三、单项链表面试题

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

（如果是带头节点的，不统计头节点）

  1. //用来查看链表中有效数据的个数
  2. //传过来一个头节点，即可得到他的长度
  3. public static int getLength(HeroNode head){
  4.     //判断如果这个链表是空链表的话 直接return 0 就行
  5.     if (head.next == null){
  6.         return 0;
  7.     }
  8.     //因为不算上 头节点，所以是 head.next
  9.     HeroNode temp = head.next;
  10.     int length = 0;
  11.     while ( temp != null){
  12.         length ++;
  13.         temp = temp.next;
  14.     }
  15.     return length;
  16. }
  17. 调用：
  18. System.out.println(HeadLinkedList.getLength(headLinkedList.getHead()));

2、查找单链表中的单数第K个节点【新浪面试题】

2.1 思路：

  1. 编写一个方法，接收 head节点，同时接收一个index
  2. index 是表示倒数第几个节点
  3. 先把链表从头到尾遍历一遍，得到长度

  4. 得到长度之后，我们从链表的第一个开始遍历（size - index）个，就可以得到了

    2.2 代码实现

    1. //用来查看链表中倒数第K个节点
    2. public static HeroNode getLast(HeroNode head, int index){
    3.  //1.首先根据头节点 得到链表的长度
    4.  //判断如果这个链表是空链表的话 直接return 0 就行
    5.  if (head.next == null){
    6.      return null;
    7.  }
    8.  //因为不算上 头节点，所以是 head.next
    9.  HeroNode temp = head.next;
    10.  int length = 0;
    11.  while ( temp != null){
    12.      length ++;
    13.      temp = temp.next;
    14.  }
    15.  //2. 做一个数据的校验，判断index是否合理
    16.  if(index <= 0 || index > length){
    17.      return null;
    18.  }
    19.  //3. 进行遍历，倒数第几个 ： 长度 - 倒数第几个 = 要找的那个
    20.  HeroNode temp2 = head;  //辅助变量，帮我们遍历
    21.  for(int i = 0; i <= length - index; i++){
    22.      if (temp2.next == null){
    23.          break;
    24.      }
    25.      temp2 = temp2.next;
    26.  }
    27.  return temp2;
    28. }

    3、单链表的反转【腾讯面试题】

    3.1 思路：

  5. 先定义一个新的节点，HeroNode reverseHead = new HeroNode();

  6. 从头到尾遍历节点，将每一个遍历的节点放到头的后面 【头插法】
    • 这样就是 1 2 3 先插入1， 然后 在往1之前插入2 在往2 之前插入3
  7. 原来链表head.next = reverseHead.next;

    3.2 代码实现【头插法】

    1. //传入一个头节点，对其进行链表反转
    2. public static void reverse(HeroNode head){
    3.  //如果链表为空 或者 链表中就一个元素，那么直接返回这个链表就行，不用反转
    4.  if (head.next == null || head.next.next == null){
    5.      return;
    6.  }
    7.  //定义一个辅助变量，帮助我们遍历链表
    8.  HeroNode cur = head.next;
    9.  //此变量永远指向 cur的下一个节点
    10.  HeroNode next = null;
    11.  //新的头节点
    12.  HeroNode reverseHead = new HeroNode(0,"","");
    13.  while (cur != null){
    14.      //保存cur的下一个节点，防止丢失
    15.      next = cur.next;
    16.      //将cur的下一个节点指向新的链表的最前端 右边的那条链子
    17.      cur.next = reverseHead.next;
    18.      //头插法，将每一个遍历的节点插入到链表的最前端  左边的那条链子
    19.      reverseHead.next = cur;
    20.      //向后移动一位
    21.      cur = next;
    22.  }
    23.  //将head.next 执行reverserHead.next 实现单链表的反转
    24.  head.next = reverseHead.next;
    25. }

    4、从尾到头打印单链表【百度面试题，要求：1.反向遍历，2。Stack栈】

    4.1 思路

  • 思路1：将单链表反转过来，然后再打印【问题：会破坏原来链表的结构】

  • 思路2：利用栈数据结构，将各个节点压入栈中，利用栈的先进后出的特点 就实现了逆序打印的效果

    4.2 代码实现：

    1. //从头到尾打印单链表，使用栈数据结构
    2. public static void reversePrint(HeroNode head){
    3.   //先判断 链表是否为空。
    4.   if(head.next == null){
    5.       return;
    6.   }
    7.   Stack<HeroNode> stack = new Stack<>();
    8.   HeroNode temp = head.next;
    9.   while (temp != null){
    10.       //把节点压入栈中【先进后出】
    11.       stack.push(temp);
    12.       //向后移动一位
    13.       temp = temp.next;
    15.   }
    16.   //将栈中的节点进行打印,因为是先进后出，所以就完成了倒序打印
    17.   while (stack.size() > 0){
    18.       System.out.println(stack.pop());
    19.   }
    20. }

    5、合并两个有序的单链表，合并之后的链表依然有序

四、双向链表

1、双向链表和单向链表有什么不一样的地方

  • 除了有data域，next域，还有一个pre域 用来保存前一个节点。

  • head头部也有pre域，可以向头部的前面加节点

    2、分析双向链表的遍历，增加，删除，修改。

    2.1遍历思路：

  • 遍历跟单链表一样，只是可以向前，也可以向后查找

    2.2 添加思路：(添加到链表的最后)

  • 先找到双向链表的最后那个节点

  • 先让 **temp.next = 新节点 **

  • 然后 **新节点.pre = temp**

    2.3 修改思路：

  • 和原来的单项链表一致，先找到节点再修改

    2.4 删除思路：

  • 因为是双向链表，所以不需要找到 删除的前一个节点，直接找到要删除的节点就行

  • 然后 **要删除的节点.pre.next = 要删除的节点.next;**
  • 再然后 **要删除的节点.next.pre = 要删除的节点.pre**
    • 需要注意的是如果是删除最后一个节点的话，就不需要最后一句了，所以加一个if判断

未命名图片.png

五、双向链表代码实现

  1. package com.yixuexi.linkedList;
  3. /**
  4. * 2020/10/11   20:57
  5. */
  6. public class DoubleLinkedListDemo {
  7.     public static void main(String[] args) {
  8.         //进行测试
  9.         //首先创建几个人物数据
  10.         DoubleHeroNode n1 = new DoubleHeroNode(1,"松江","及时雨");
  11.         DoubleHeroNode n2 = new DoubleHeroNode(2,"李逵","黑旋风");
  12.         DoubleHeroNode n3 = new DoubleHeroNode(3,"吴用","智多星");
  13.         DoubleHeroNode n4 = new DoubleHeroNode(4,"卢俊义","玉麒麟");
  14.         DoubleHeroNode n5 = new DoubleHeroNode(5,"武大郎","烧饼哥");
  16.         //创建链表
  17.         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  18.         doubleLinkedList.add(n1);
  19.         doubleLinkedList.add(n2);
  20.         doubleLinkedList.add(n3);
  21.         doubleLinkedList.add(n4);
  22.         doubleLinkedList.add(n5);
  24.         //查看链表中的数据
  25.         doubleLinkedList.list();
  27.         //删除表中的数据
  28.         doubleLinkedList.delete(1);
  29.         doubleLinkedList.delete(5);
  31.         System.out.println("-------------------------------->");
  32.         //查看链表中的数据
  33.         doubleLinkedList.list();
  35.         DoubleHeroNode n6 = new DoubleHeroNode(5,"潘金莲","烧饼哥老婆");
  36.         doubleLinkedList.update(n6);
  37.         System.out.println("-------------------------------->");
  38.         //查看链表中的数据
  39.         doubleLinkedList.list();
  40.     }
  41. }
  43. //
  44. class DoubleLinkedList{
  45.     //在这个单项链表类中有一个 头节点，这个头节点不能动
  46.     private DoubleHeroNode head = new DoubleHeroNode(0, "", "");
  48.     public DoubleHeroNode getHead() {
  49.         return head;
  50.     }
  51.     //遍历的方法
  52.     //用来展示链表中的数据
  53.     public void list() {
  54.         //使用一个temp辅助变量来帮助我们进行循环遍历
  55.         DoubleHeroNode temp = head;
  56.         //首先判断一下这个链表是否为空链表
  57.         //如果头节点的next域 为空则表示没有下一个节点，为空链表
  58.         if (temp.next == null) {
  59.             return;
  60.         }
  61.         // 因为上面做了判断了，所以直接输出就行
  62.         //然后把temp往后移动一位，如果temp.next为空，则表示到头了
  63.         while (true) {
  64.             System.out.println(temp.next);
  65.             temp = temp.next;
  66.             if (temp.next == null) {
  67.                 break;
  68.             }
  69.         }
  70.     }
  72.     //用来添加节点的方法【从链表的尾部添加】
  73.     public void add(DoubleHeroNode doubleHeroNode) {
  74.         //由于每次添加节点都是往链表的最后去添加，所以先要遍历一遍链表，找出最后那个元素
  75.         //这里遍历我们使用一个 temp临时变量 辅助我们遍历
  76.         //这里这个temp就是头节点，使用循环，如果temp.next == null，则表示它是最后一个节点
  77.         //如果 temp.next != null 则表示它不是最后一个节点，则往后移一位， temp = temp.next;
  78.         DoubleHeroNode temp = head;
  79.         while (true) {
  80.             if (temp.next == null) {
  81.                 //说明此时 temp是最后一个节点 直接跳出循环
  82.                 break;
  83.             }
  84.             //能执行到这里，则表示不是最后一个节点，往后移动一位，继续循环
  85.             temp = temp.next;
  86.         }
  87.         //执行到这里，说明此时的temp一定为最后一个节点，直接将节点添加到 temp.next 然后把添加的元素.pre = temp
  88.         temp.next = doubleHeroNode;
  89.         doubleHeroNode.pre = temp;
  91.     }
  93.     //删除元素的方法
  94.     public void delete(int index){
  95.         DoubleHeroNode temp = head;
  96.         boolean flag = false;
  97.         while (true){
  98.             if (temp == null){
  99.                 return;
  100.             }
  101.             if (temp.id == index){
  102.                 flag = true;
  103.                 break;
  104.             }
  105.             temp = temp.next;
  106.         }
  107.         if (flag){
  108.             temp.pre.next = temp.next;
  109.             //这里代码有问题，如果是删除的最后一个节点的话会报出空指针异常,所以需要加上if判断
  110.             if (temp.next != null){
  111.                 temp.next.pre = temp.pre;
  112.             }
  113.         }else{
  114.             System.out.println("没有找到你要删除的节点");
  115.         }
  117.     }
  119.     public void update(DoubleHeroNode doubleHeroNode){
  120.         //需要使用一个辅助变量 temp
  121.         DoubleHeroNode temp = head;
  122.         //首先判断是否为空，如果为空直接退出
  123.         if (temp.next == null) {
  124.             System.out.println("链表为空，请加入节点后在进行更新！");
  125.             return;
  126.         }
  127.         //使用循环找出id为 newHeroNode.id 的节点
  128.         Boolean flag = false;
  129.         while (true) {
  130.             if (temp == null) {
  131.                 break;
  132.             }
  133.             //如果找到了 那么直接跳出循环，因为当前temp 就是需要修改的节点
  134.             if (temp.id == doubleHeroNode.id) {
  135.                 flag = true;
  136.                 break;
  137.             }
  138.             //没有找到则向后移动一位
  139.             temp = temp.next;
  140.         }
  141.         //判断 如果flag为true 则表示当前temp是需要修改的
  142.         if (flag) {
  143.             temp.name = doubleHeroNode.name;
  144.             temp.nickname = doubleHeroNode.nickname;
  146.         } else {
  147.             System.out.println("没有找到对应id的节点，请输入正确的数据");
  148.         }
  151.     }
  152. }
  156. //创建一个有着双向节点的类
  157. class DoubleHeroNode {
  158.     public int id;
  159.     public String name;
  160.     public String nickname;
  161.     public DoubleHeroNode next;  //表示双向链表中的next区域，存放下一个节点
  162.     public DoubleHeroNode pre;   //表示双向链表中的pre区域，存放上一个节点
  163.     //构造器，
  164.     public DoubleHeroNode(int id, String name, String nickname) {
  165.         this.id = id;
  166.         this.name = name;
  167.         this.nickname = nickname;
  168.     }
  170.     @Override
  171.     public String toString() {
  172.         return "DoubleHeroNode{" +
  173.                 "id=" + id +
  174.                 ", name='" + name + '\'' +
  175.                 ", nickname='" + nickname + '\'' +
  176.                 '}';
  177.     }
  178. }

六、单向环形链表

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

约瑟夫问题：
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

假设：
n = 5 表示有几个人
k = 1 表示从第1个人 开始报数
m = 2 表示数两下【自身是1下，第二下那个人出列】然后第三个人数
最后出队列的顺序是 2->4->1->5->3
解决方案：使用单向环形链表，没有头节点，最后一个节点指向第一个节点

2、创建环形链表的思路

  • 先创建第一个节点，让first节点指向该节点，这样就形成了环状

  • 后面当我们没创建一个新的节点，就把该节点加入到以后的环形链表中即可。

    3、遍历环形链表的思路

  • 让一个辅助变量 curboy，指向first节点，

  • 然后通过一个while循环进行遍历
  • 再循环中 如果curboy.next = first 则可以break了，因为 前遍历的下一个节点是 第一个节点 则表示遍历完了

    未命名图片.png

    4、约瑟夫问题思路

    未命名图片.png

    约瑟夫问题代码实现

    ```java package com.yixuexi.linkedList;

/**

  • 2020/10/12 19:20 / /解决约瑟夫问题，模拟环形链表*/ public class Josepfu { public static void main(String[] args) {
    1.   CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
    2.   circleSingleLinkedList.addBoy(5);
    3.   circleSingleLinkedList.showBoy(); 
    4.   circleSingleLinkedList.countBoy(1,2,5);
    }

}

class CircleSingleLinkedList{ //创建一个 first 指针，这个指针永远指向 第一个节点。 public Boy first = null;

  1. //创建环形链表
  2. public void addBoy(int nums){
  3.     //首先判断传进来的值合不合法，如果说构建一个小于1 个环形链表 那完全没必要
  4.     if (nums < 1){
  5.         System.out.println("构建链表节点数量太少，没必要！");
  6.         return;
  7.     }
  8.     //创建一个辅助指针，帮助我们创建环形链表
  9.     Boy curBoy = null;
  10.     //进行构建
  11.     for (int i = 1; i <= nums; i ++){
  12.         //每循环一次，创建一个小孩
  13.         Boy boy = new Boy(i);
  14.         //如果是创建第一个小孩，那么这时第一个节点，让first指向这个第一个节点
  15.         if ( i == 1 ){
  16.             first = boy;
  17.             //再将first的下一个节点指向boy，形成一个环
  18.             first.setNext(boy);
  19.             //让辅助节点指向first
  20.             curBoy = first;
  21.         }else{
  22.             //倒数第二个节点的next 指向倒数第一个节点
  23.             curBoy.setNext(boy);
  24.             //将最后一个节点指向第一个节点，形成一个环
  25.             boy.setNext(first);
  26.             //向后一位移动
  27.             curBoy = boy;
  28.         }
  29.     }
  32. }
  33. //遍历当前的单项环形链表
  34. public void showBoy(){
  35.     if (first == null){
  36.         System.out.println("空链表，没有必要做遍历");
  37.         return;
  38.     }
  40.     Boy curBoy = first;
  41.     while (true){
  42.         System.out.println("小孩的编号为：" + curBoy.getNo());
  43.         //因为是环形链表，所以说 如果当前遍历的下一个节点是 第一个节点 则表示遍历完了
  44.         if (curBoy.getNext() == first){
  45.             break;
  46.         }
  47.         //向后移动一位
  48.         curBoy = curBoy.getNext();
  49.     }
  51. }
  52. // 根据用户的输入，计算出小孩出圈的顺序
  53. /**
  54.  *
  55.  * @param starNo 表示从第几个小孩开始数
  56.  * @param countNum 表示数几下
  57.  * @param nums 表示最初有几个小孩在圈中
  58.  */
  59. public void countBoy(int starNo,int countNum, int nums){
  60.     //先对数据进行一波校验
  61.     if (first == null || starNo < 1 || starNo > nums){
  62.         System.out.println("输入的参数有误，请重新输入");
  63.         return;
  64.     }
  65.     //创建辅助节点，帮助完成小孩出圈
  66.     Boy helper = first;
  67.     //将helper 移动到这个链表的最后一个节点
  68.     while (true){
  69.         if (helper.getNext() == first){
  70.             break;
  71.         }
  72.         //向后移动一位
  73.         helper = helper.getNext();
  74.     }
  75.     //在小孩报数前，先让first 和 helper移动 k-1 次
  76.     for (int j = 0; j < starNo - 1; j ++){
  77.         first = first.getNext();
  78.         helper = helper.getNext();
  79.     }
  81.     //当小孩报数时，让first和helper指针同时移动 m -1次，然后出圈
  82.     //通过循环，让这个链表中 到最后只剩下一个节点
  83.     while (true){
  84.         if (helper == first){
  85.             break;
  86.         }
  87.         //让first和helper同时的移动 countNum - 1
  88.         for (int i = 0; i < countNum -1 ; i++){
  89.             first = first.getNext();
  90.             helper = helper.getNext();
  91.         }
  92.         //此时的first 指向的就是要出圈小孩的节点，
  93.         System.out.println(first.getNo());
  94.         //将小孩出圈
  95.         first = first.getNext();
  96.         helper.setNext(first);
  97.     }
  98.     System.out.println("最后留在圈中的小孩的编号为 " + first.getNo());
  99. }

}

//小孩节点 class Boy{ private int no; //小孩id private Boy next;

  1. public Boy(int no) {
  2.     this.no = no;
  3. }
  5. public int getNo() {
  6.     return no;
  7. }
  9. public void setNo(int no) {
  10.     this.no = no;
  11. }
  13. public Boy getNext() {
  14.     return next;
  15. }
  17. public void setNext(Boy next) {
  18.     this.next = next;
  19. }

}

```