一、单向链表

1、链表是有序结构

（1）带头单链表内存中的存储：

image.png 1、链表是以节点的方式来存储,是链式存储
2、每个节点包含 data 域， next 域：指向下一个节点.
3、如图：发现链表的各个节点不一定是连续存储.
4、链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

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

image.png 1、逻辑上看就是，根据头连续，但是内存中的排布则未必连续存储
2、就像你的爷爷，父亲，你(三代人，是连续的)，但是你们三人家族在这个世界
不同的角落，身边出现的可能是其他家族的人，他们也是这样的连续子代关系
3、宗族看逻辑图，世界看内存图(世界是广度现实)

(3)小结：

对这两幅图，我想了一个口令：逻辑有序，内存无序

2、单链表：直接插入(按插入顺序插入)，无考虑到排行

(1)思路：

image.png 一、添加（创建）
1、先创建一个head 头节点， 作用就是表示单链表的头
2、后面我们每添加一个节点，就直接加入到 链表的最后
二、遍历：
1、通过一个辅助变量遍历，帮助遍历整个链表，为null 终止


(2)代码：

  1. package com.kk.datastructure.linkedlist;
  3. public class SingleLinkedListDemo {
  5.     public static void main(String[] args) {
  6.         //先创建节点
  7.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  8.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  9.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  10.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  12.         //创建要给链表
  13.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  16.         //加入
  17.         singleLinkedList.add(hero1);
  18.         singleLinkedList.add(hero4);
  19.         singleLinkedList.add(hero2);
  20.         singleLinkedList.add(hero3);
  22.         singleLinkedList.list();
  24.     }
  26. }
  28. //定义HeroNode ， 每个HeroNode 对象就是一个节点
  29. class HeroNode {
  30.     public int no;         // 好汉排行
  31.     public String name;    // 好汉姓名
  32.     public String nickname;// 好汉外号
  33.     public HeroNode next;  //指向下一个节点（好汉）
  34.     //构造器
  35.     public HeroNode(int no, String name, String nickname) {
  36.         this.no = no;
  37.         this.name = name;
  38.         this.nickname = nickname;
  39.     }
  40.     //为了显示方法，我们重新toString
  41.     @Override
  42.     public String toString() {
  43.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  44.     }
  46. }
  48. // 定义 SingleLinkedList 管理梁山英雄
  49. class SingleLinkedList{
  50.     // 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
  51.     private HeroNode head = new HeroNode(0, null, null);
  53.     // 返回头结点
  54.     public HeroNode getHead() {
  55.         return head;
  56.     }
  58.     // 添加节点到单向链表
  59.     // 思路，当不考虑编号顺序时
  60.     // 1. 找到当前链表的最后节点
  61.     // 2. 将最后这个节点的next 指向 新的节点
  62.     public void add(HeroNode heroNode) {
  63.         // 因为head节点不能动，因此我们需要一个辅助变量 temp（可以理解为晁天王）
  64.         HeroNode temp = head;
  65.         // 遍历链表，找到最后
  66.         while(true) {
  67.             // 找到链表的最后是null 
  68.             if(temp.next == null)break;
  69.             // 若没有找到最后，则后移(这里是n+1次的，n个有效数据)
  70.             temp = temp.next;
  71.         }
  72.         // 当退出while循环时，temp就指向了链表的最后
  73.         // 将最后这个节点的next 指向 新的节点
  74.         temp.next = heroNode;               
  75.     }
  77.     // 遍历链表
  78.     public void list() {
  79.         // 判断链表是否为空
  80.         if (head.next == null) {
  81.             System.out.println("链表为空~~~");
  82.             return;
  83.         }
  84.         // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  85.         HeroNode temp = head.next;
  87.         while (true) {
  88.             // 判断是否到链表的最后
  89.             if (temp == null)
  90.                 return;
  92.             // 输出节点信息
  93.             System.out.println(temp);
  94.             // 将节点后移，注意要加！！
  95.             temp = temp.next;
  96.         }
  97.     }
  98. }


(3)缺点：

1、无法按照英雄编号排序，只能按照插入顺序。
2、并且重复了同排行序号的英雄，也随意可以添加，这是在梁山不被允许的。

3、单链表：按顺序插入，删除，修改，重复排行不得添加

(1)添加<按照编号顺序>的思路：

3、链表 - 图4 1、首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
2、新的节点 a，a.next = temp.next
3、将temp.next = a ，新的节点

(2)修改：

编号不变，姓名和外号可变

(3)删除节点的思路

3、链表 - 图5 1、我们先找到 需要删除的这个节点的前一个节点 temp
2、temp.next = temp.next.next
3、被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

(4)以上增、改、删的代码：

  1. package com.kk.datastructure.linkedlist.improve;
  4. public class SingleLinkedListDemo {
  6.     public static void main(String[] args) {
  7.         //先创建节点
  8.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  9.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  10.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  11.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  13.         //创建要给链表
  14.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  16.         singleLinkedList.addByOrder(hero1);
  17.         singleLinkedList.addByOrder(hero4);
  18.         singleLinkedList.addByOrder(hero2);
  19.         singleLinkedList.addByOrder(hero3);
  21.         // singleLinkedList.addByOrder(hero3);      
  22.         // singleLinkedList.list();
  24.         // 修改
  25. //      singleLinkedList.update(new HeroNode(1, "送浆", "白日"));
  26. //      singleLinkedList.list();
  28.         // 删除
  29.         singleLinkedList.delete(1);
  30.         singleLinkedList.delete(2);
  31.         singleLinkedList.delete(3);
  32.         singleLinkedList.delete(4);
  33.         singleLinkedList.list();
  35.     }
  37. }
  39. //定义HeroNode ， 每个HeroNode 对象就是一个节点
  40. class HeroNode {
  41.     public int no;         // 好汉排行
  42.     public String name;    // 好汉姓名
  43.     public String nickname;// 好汉外号
  44.     public HeroNode next;  //指向下一个节点（好汉）
  45.     //构造器
  46.     public HeroNode(int no, String name, String nickname) {
  47.         this.no = no;
  48.         this.name = name;
  49.         this.nickname = nickname;
  50.     }
  51.     //为了显示方法，我们重新toString
  52.     @Override
  53.     public String toString() {
  54.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  55.     }
  57. }
  59. // 定义 SingleLinkedList 管理梁山英雄
  60. class SingleLinkedList{
  61.     // 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
  62.     private HeroNode head = new HeroNode(0, null, null);
  64.     // 返回头结点
  65.     public HeroNode getHead() {
  66.         return head;
  67.     }
  69.     // 删除   
  70.     //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
  71.     //2. 说明我们在比较时，是temp.next.no 和  需要删除的节点的no比较
  72.     public void delete(int no) {
  73.         HeroNode temp = head;
  74.         boolean flag = false;// 标志是否找到待删除节点
  75.         while(true) {
  76.             if(temp.next ==null)
  77.                 // 已经到链表的最后
  78.                 break;
  79.             if(temp.next.no == no) {
  80.                 // 已经找到
  81.                 flag = true;
  82.                 break;
  83.             }
  84.             // 移动继续找
  85.             temp = temp.next;
  86.         }
  87.         // 通过 flag 进行判断
  88.         if(flag) {
  89.             // 已经找到，指向后一个引用
  90.             temp.next = temp.next.next;
  91.         }else 
  92.             System.out.printf("没有找到排行为【%d】要修改的英雄",no);      
  93.     }
  95.     // 更新节点的信息, 根据no编号来修改，即no编号不能改
  96.     public void update(HeroNode heroNode) {
  97.         // 判空
  98.         if(head.next == null) {
  99.             System.out.println("链表为空~~");
  100.             return;
  101.         }
  102.         // 根据 no 找到需要修改的节点
  103.         // 定义一个辅助变量
  104.         HeroNode temp = head.next;
  105.         boolean flag = false;// 表示是否找到节点
  106.         while (true) {
  107.             if (temp == null)
  108.                 // 链表已经遍历完
  109.                 break;
  110.             if(temp.no == heroNode.no) {
  111.                 // 节点已经找到
  112.                 flag = true;
  113.                 break;
  114.             }
  115.             // 节点移动，继续找
  116.             temp = temp.next;
  117.         }
  119.         // 根据 flag 判断
  120.         if(flag) {
  121.             // 找到，修改姓名和外号
  122.             temp.name = heroNode.name;
  123.             temp.nickname = heroNode.nickname;
  124.         }else {
  125.             System.out.printf("没有找到排行为【%d】要修改的英雄",heroNode.no);
  126.         }
  127.     }
  129.     // 按编号顺序添加（如果有这个排名，则添加失败，并给出提示）
  130.     public void addByOrder(HeroNode heroNode) {
  131.         // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  132.         // 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
  133.         HeroNode temp = head;
  134.         boolean flag = false;// flag标志添加的编号是否存在，默认为false
  135.         while(true) {
  136.             if(temp.next == null) break;
  137.             if(temp.next.no > heroNode.no)
  138.                 // 位置找到，就在 temp后面
  139.                 // 因为 它满足了 按顺序 ，所以可以插入
  140.                 break;
  141.             if(temp.next.no == heroNode.no) {
  142.                 // 已经存在改排行的编号(不可重复)
  143.                 flag = true;
  144.                 break;
  145.             }
  146.             // 没满足以上，后移下一次节点继续找
  147.             temp = temp.next;
  148.         }
  150.         // 对 flag 进行判断
  151.         if(flag) 
  152.             // 不能添加，说明编号已经存在
  153.             System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
  154.         else {
  155.             // 插入到链表中，temp的后面
  156.             heroNode.next = temp.next;// 我后面的是6号，现在你后面是6号
  157.             temp.next = heroNode;// 我后面是你
  158.         }
  159.     }
  162.     // 遍历链表
  163.     public void list() {
  164.         // 判断链表是否为空
  165.         if (head.next == null) {
  166.             System.out.println("链表为空~~~");
  167.             return;
  168.         }
  169.         // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  170.         HeroNode temp = head.next;
  172.         while (true) {
  173.             // 判断是否到链表的最后
  174.             if (temp == null)
  175.                 return;
  177.             // 输出节点信息
  178.             System.out.println(temp);
  179.             // 将节点后移，注意要加！！
  180.             temp = temp.next;
  181.         }
  182.     }
  183. }

4、单向链表经典面试题(新浪，百度，腾讯) —- 5题

1、题目以及思路：

1、求单链表中有效节点的个数
(1)遍历节点后的个数即可
2、查找单链表中的倒数第k个结点 【新浪面试题】
(1) 有效的总长度 - 要查询的位置 = 倒数的位置 【8-2=6】

3、单链表的反转【腾讯面试题，有点难度】image.pngimage.png (1)先定义一个节点 reverseHead = new HeroNode()
(2)从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
(3)原来的链表的head.next = reverseHead.next

4、从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
(1) 方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议
(2) 方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果. image.png 5、合并两个有序的单链表，合并之后的链表依然有序
(1)创建一个新链表，然后比较两个链表谁排行高，则先存入新链表中 image.png

1-2-3-4-5 五题的代码：

  1. package com.datastructure.linkedlist.interview;
  3. import java.util.Stack;
  5. public class SingleLinkedListInterview {
  7.     /**
  8.      * @param args
  9.      */
  10.     public static void main(String[] args) {
  12.         // 先创建节点
  13.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  14.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  15.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  16.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  17.         HeroNode hero5 = new HeroNode(5, "鲁智深", "花和尚");
  18.         HeroNode hero6 = new HeroNode(6, "武松", "行者");
  20.         // 创建要给链表
  21.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  23. //      singleLinkedList.addByOrder(hero1);
  24. //      singleLinkedList.addByOrder(hero4);
  25. //      singleLinkedList.addByOrder(hero2);
  26. //      singleLinkedList.addByOrder(hero3);
  28.         singleLinkedList.list();
  30.         // 有效个数
  31.         int length = singleLinkedList.getLength(singleLinkedList.getHead());
  32.         System.out.printf("有效个数为：%d\n",length);
  34.         // 倒数第 K 的节点
  35.         HeroNode resultNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 3);
  36.         System.out.println(resultNode);
  38.         // 链表反转
  39.         singleLinkedList.reversetList(singleLinkedList.getHead());
  40.         singleLinkedList.list();
  42.         // 利用栈反向打印
  43.         singleLinkedList.reversetPrint(singleLinkedList.getHead());
  45.         System.out.println("--------------------美丽的分割线---------------------------");
  47.         SingleLinkedList singleLinkedList1 = new SingleLinkedList();
  48.         SingleLinkedList singleLinkedList2 = new SingleLinkedList();
  50.         singleLinkedList1.add(hero6);
  51.         singleLinkedList1.add(hero2);
  52.         singleLinkedList1.add(hero4);
  53.         singleLinkedList2.add(hero5);
  54.         singleLinkedList2.add(hero1);
  55.         singleLinkedList2.add(hero3);
  57. //      singleLinkedList1.list();
  58. //      singleLinkedList2.list();
  60.         System.out.println("--------------------美丽的分割线---------------------------");
  62.         HeroNode newHead = singleLinkedList.sumLinkedList(singleLinkedList1.getHead(),
  63.                 singleLinkedList2.getHead());
  65.         SingleLinkedList singleLinkedList3 = new SingleLinkedList();
  66.         singleLinkedList3.setHead(newHead);
  67.         singleLinkedList3.list();
  70.     }
  72. }
  74. //定义 SingleLinkedList 管理梁山英雄
  75. class SingleLinkedList {
  76.     // 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
  77.     private HeroNode head = new HeroNode(0, null, null);
  79.     // 返回头结点
  80.     public HeroNode getHead() {
  81.         return head;
  82.     }
  84.     public void setHead(HeroNode head) {
  85.         this.head = head;
  86.     }
  89.     /**
  90.      * 题目五：合并两个有序的单链表，合并之后的链表依然有序
  91.      * @param head1
  92.      * @param head2
  93.      * 想了很久，有两个解法：只实现方案一
  94.      * 方案一：遍历A 链表找出最小的号，再遍历B链表找出最小，然后比较
  95.      * 小的先插入到新链表中，依次重复(每一次最小的，要被摘除)--有问题未解决
  96.      * 方案二：就是模仿数组的冒泡排序，左右比较交换，未实现
  97.      * @return
  98.      */
  99.     public static HeroNode sumLinkedList(HeroNode head1,HeroNode head2) {
  100.         // 判空
  101.         if(head1.next ==null || head2.next == null)return null;
  102.         // 定义一个新链表 用于存储合并
  103.         //SingleLinkedList singleLinkedList = new SingleLinkedList();
  104.         // 定义一个新链表的头
  105.         HeroNode newHead = new HeroNode(0, "", "");
  106.         // 先合并再排序
  107.         // 合并 head1 链表最后一个接  head2的后米面一个
  108.         HeroNode cuc1 = head1.next;
  109.         HeroNode temp = null;
  110.         while(cuc1!=null) {
  111.             // 最后一个为null 将他前一个先保存
  112.             temp = cuc1;
  113.             cuc1 = cuc1.next;
  114.         }
  115.         // head2 绑定head1 的后面一个
  116.         temp.next = head2.next;
  118.         // 现在已经输合并的无序链表 head1
  119.         // 遍历得到最小
  120.         HeroNode minNode = null;
  121.         // 最小的前一个，用于摘除原始最小
  122.         HeroNode minNodeFront = null;
  123.         // 辅助遍历最小
  124.         HeroNode minTemp1 =  head1.next;
  125.         // 填充 次数为 链表长度
  126.         int lengt1 = SingleLinkedList.getLength(newHead);
  127.         int lengt2 = SingleLinkedList.getLength(head1);
  128.         while(SingleLinkedList.getLength(newHead)<=lengt2)
  129.         {
  130.             while(minTemp1.next != null) {
  131.                 minNode = minTemp1;
  132.                 // 临时保存 用于摘除它后面的
  133.                 //HeroNode minTemp2 = minTemp1;
  134.                 if(minNode.no > minNode.next.no) {
  135.                     // 赋值
  136.                     minNodeFront = minTemp1;
  137.                     minNode = minNode.next;
  139.                 }
  140.                 // 后移
  141.                 minTemp1 = minTemp1.next;
  142.             }
  143.             // 摘除最小
  144.             minNodeFront.next = minNodeFront.next.next;
  145.             // 绑定到 新链表
  146.             minNode.next = newHead.next;
  147.             newHead.next = minNode;
  148.         }
  150.         return newHead;
  151.     }
  153.     /**
  154.      * 题目四：反向打印链表(栈)
  155.      * @param head
  156.      */
  157.     public static void reversetPrint(HeroNode head) {
  158.         // 判空
  159.         if(head.next == null)return;
  161.         // 创建一个栈，用于节点出入栈，实现反向打印
  162.         Stack<HeroNode> stack = new Stack();
  163.         // 定义辅助指针，用于遍历原始链表
  164.         HeroNode cuc = head.next;
  165.         // 将链表所有节点入栈
  166.         while (cuc != null) {
  167.             stack.push(cuc);// 节点 入栈
  168.             cuc = cuc.next;// 节点后移
  169.         }
  170.         // 所有节点依次出栈
  171.         while( stack.size() >0) {
  172.             //stack的特点是先进后出
  173.             System.out.println(stack.pop());
  174.         }
  175.     }
  177.     /**
  178.      * 题目三：单链表的反转【腾讯面试题，有点难度】
  179.      * 
  180.      * @param head
  181.      */
  182.     public static void reversetList(HeroNode head) {
  183.         // 若链表为空，或者只有一个则不需要反转
  184.         if (head.next == null || head.next.next == null) {
  185.             return;
  186.         }
  187.         // 定义一个辅助指针，用户遍历原始未反转的那个链表
  188.         HeroNode cuc = head.next;
  189.         // 用于动态指向 当前节点【cuc】的 下一个节点
  190.         HeroNode next = null;
  191.         // 新链表(反转后的)的链表头
  192.         HeroNode reversetHead = new HeroNode(0, "", "");
  193.         // 思路： 遍历原始链表，没遍历一个节点将其取出，并放在新链表头(reversetHead)的后面的最前端
  194.         // 每一个新节点，都会取代旧的，与新链表头牵手
  195.         while (cuc != null) {
  196.             // 暂时先保存当前节点的下一个节点，用于后移
  197.             next = cuc.next;
  198.             // 将要 遍历出来的新节点，指向 新链表头 后面的最前端(将情敌的手，从她手上拨开)
  199.             cuc.next = reversetHead.next;
  200.             // 将 cuc 连接到 新的链表头后面的最前端(她的手和你牵了)
  201.             reversetHead.next = cuc;
  202.             // cuc 后移，换下一个情敌来打你
  203.             cuc = next;
  204.         }
  205.         // 将head.next 指向 reverseHead.next , 实现单链表的反转
  206.         // 新链表(她)池塘养的鱼和旧链表头(她的闺蜜)共享
  207.         head.next = reversetHead.next;
  208.     }
  210.     /**
  211.      * 题目二：查找单链表中的倒数第k个结点 【新浪面试题】
  212.      * 
  213.      * @param head     传入的头结点
  214.      * @param HeroNode 需要查找的 倒数节点数据
  215.      * @return
  216.      */
  217.     // 思路：
  218.     // 1、先遍历得到 有效数据个数（总长度--不包括头节点）
  219.     // 2、有效个数 - index = 倒数 K(size-index = k )
  220.     // 3、找到则返回当前节点，找不到返回 null
  221.     public static HeroNode findLastIndexNode(HeroNode head, int index) {
  222.         // 判空
  223.         if (head.next == null)
  224.             return null;
  226.         // 第一个遍历得到链表的长度(节点个数)
  227.         int size = getLength(head);
  229.         // 第二次遍历 size-index 位置，就是我们倒数的第K个节点
  230.         // 先做一个index的校验
  231.         if (index <= 0 || index > size) {
  232.             // 查找的位置不能大过总长
  233.             return null;
  234.         }
  236.         // 定义给辅助变量， for 循环定位到倒数的index
  237.         HeroNode cuc = head.next;// 8-2=6,倒数第二个就是第六个
  238.         for (int i = 0; i < size - index; i++) {
  239.             cuc = cuc.next;
  240.         }
  241.         return cuc;
  242.     }
  244.     /**
  245.      * 题目一：获取有效节点个数
  246.      * 
  247.      * @param head 头结点(不统计)
  248.      * @return 返回有效节点个数
  249.      */
  250.     public static int getLength(HeroNode head) {
  251.         // 判空
  252.         if (head.next == null)
  253.             return 0;
  254.         int length = 0;
  255.         // 定义辅助变量 cuc,此处没有统计 头节点
  256.         HeroNode cuc = head.next;
  257.         while (cuc != null) {
  258.             length++;
  259.             cuc = cuc.next;// 指向下一个，继续遍历
  260.         }
  261.         return length;
  262.     }
  264.     // 按编号顺序添加（如果有这个排名，则添加失败，并给出提示）
  265.     public void addByOrder(HeroNode heroNode) {
  266.         // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  267.         // 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
  268.         HeroNode temp = head;
  269.         boolean flag = false;// flag标志添加的编号是否存在，默认为false
  270.         while (true) {
  271.             if (temp.next == null)
  272.                 break;
  273.             if (temp.next.no > heroNode.no)
  274.                 // 位置找到，就在 temp后面
  275.                 // 因为 它满足了 按顺序 ，所以可以插入
  276.                 break;
  277.             if (temp.next.no == heroNode.no) {
  278.                 // 已经存在改排行的编号(不可重复)
  279.                 flag = true;
  280.                 break;
  281.             }
  282.             // 没满足以上，后移下一次节点继续找
  283.             temp = temp.next;
  284.         }
  286.         // 对 flag 进行判断
  287.         if (flag)
  288.             // 不能添加，说明编号已经存在
  289.             System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
  290.         else {
  291.             // 插入到链表中，temp的后面
  292.             heroNode.next = temp.next;// 我后面的是6号，然后我上前走过去，你走了，现在你后面是6号
  293.             temp.next = heroNode;// 我后面是你，上下两句顺序不可对调
  294.         }
  295.     }
  297.      public void add(HeroNode heroNode) {
  298.             // 因为head节点不能动，因此我们需要一个辅助变量 temp（可以理解为晁天王）
  299.             HeroNode temp = head;
  300.             // 遍历链表，找到最后
  301.             while(true) {
  302.                 // 找到链表的最后是null 
  303.                 if(temp.next == null)break;
  304.                 // 若没有找到最后，则后移(这里是n+1次的，n个有效数据)
  305.                 temp = temp.next;
  306.             }
  307.             // 当退出while循环时，temp就指向了链表的最后
  308.             // 将最后这个节点的next 指向 新的节点
  309.             temp.next = heroNode;               
  310.         }
  312.     // 遍历链表
  313.     public void list() {
  314.         // 判断链表是否为空
  315.         if (head.next == null) {
  316.             System.out.println("链表为空~~~");
  317.             return;
  318.         }
  319.         // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  320.         HeroNode temp = head.next;
  322.         while (true) {
  323.             // 判断是否到链表的最后
  324.             if (temp == null)
  325.                 return;
  327.             // 输出节点信息
  328.             System.out.println(temp);
  329.             // 将节点后移，注意要加！！
  330.             temp = temp.next;
  331.         }
  332.     }
  333. }
  335. //定义HeroNode ， 每个HeroNode 对象就是一个节点
  336. class HeroNode {
  337.     public int no; // 好汉排行
  338.     public String name; // 好汉姓名
  339.     public String nickname;// 好汉外号
  340.     public HeroNode next; // 指向下一个节点（好汉）
  341.     // 构造器
  343.     public HeroNode(int no, String name, String nickname) {
  344.         this.no = no;
  345.         this.name = name;
  346.         this.nickname = nickname;
  347.     }
  349.     // 为了显示方法，我们重新toString
  350.     @Override
  351.     public String toString() {
  352.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  353.     }
  354. }

二、双向链表

1、双向链表的操作分析和实现

管理单向链表的缺点分析:

1) 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2) 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
3) 分析了双向链表如何完成遍历，添加，修改和删除的思路

双向链表分析思路：

image.png
对上图的说明:
分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现 1) 遍历 方和 单链表一样，只是可以向前，也可以向后查找
2) 添加 (默认添加到双向链表的最后)
(1) 先找到双向链表的最后这个节点
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp;
3) 修改 思路和 原来的单向链表一样.
4) 删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;

代码实现：

  1. package com.atguigu.linkedlist;
  4. public class DoubleLinkedListDemo {
  6.     public static void main(String[] args) {
  8.         //测试一下
  9.         //县创建节点
  10.         HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
  11.         HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
  12.         HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
  13.         HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
  14.         //创建一个双向链表
  15.         DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  16.         //添加节点
  17.         doubleLinkedList.add(hero1);
  18.         doubleLinkedList.add(hero2);
  19.         doubleLinkedList.add(hero3);
  20.         doubleLinkedList.add(hero4);
  22.         //输出链表
  23.         doubleLinkedList.list();
  25.         //修改链表
  26.         HeroNode2 newHeroNode = new HeroNode2(2,"秦明","霹雳火");
  27.         doubleLinkedList.update(newHeroNode);
  28.         System.out.println("修改后的链表情况");
  29.         //输出链表
  30.         doubleLinkedList.list();
  32.         //删除链表
  33.         doubleLinkedList.del(3);
  34.         System.out.println("删除后的链表");
  35.         //输出链表
  36.         doubleLinkedList.list();
  41.     }
  43. }
  47. //创建一个双向链表的类
  48. class DoubleLinkedList{
  50.     //先初始化一个头结点，头结点不要动
  51.     private HeroNode2 head = new HeroNode2(0, "", "");
  53.     //返回头结点
  54.     public HeroNode2 getHead(){
  55.         return head;
  56.     }
  60.     //遍历双向链表
  61.     //显示链表，遍历
  62.     public void list() {
  63.         //判断链表是否为空
  64.         if (head.next == null) {
  65.             System.out.println("链表为空");
  66.             return;
  67.         }
  68.         //因为head节点不能动，因此需要一个辅助变量temp遍历
  69.         HeroNode2 temp = head.next;
  70.         while (true) {
  71.             //指向链表最后
  72.             if (temp == null) {
  73.                 break;
  74.             }
  75.             //输出节点信息
  76.             System.out.println(temp);
  77.             //将temp后移，一定小心
  78.             temp = temp.next;
  79.         }
  81.     }
  84.     //添加对象到双向链表末尾
  85.     public void add(HeroNode2 heroNode) {
  87.         //因为head节点不能动，因此需要一个辅助变量temp遍历
  88.         HeroNode2 temp = head;
  89.         //比那里链表，找到最后
  90.         while (true) {
  91.             //指向链表最后
  92.             if (temp.next == null) {
  93.                 break;
  94.             }
  95.             //如果没有找到最后，将temp后移
  96.             temp = temp.next;
  97.         }
  98.         //当退出while循环的时候，temp就指向了链表的最后
  99.         //形成一个双向链表
  100.         temp.next = heroNode;
  101.         heroNode.pre = temp;
  103.     }
  106.     //删除某个节点
  107.     //1、对于双向链表，可以直接找到亚删除的节点
  108.     //2、
  109.     public void del(int no){
  111.         //判断当前链表是否为空
  112.         if(head.next == null){
  113.             System.out.println("链表为空");
  114.             return;
  115.         }
  116.         HeroNode2 temp =head.next;
  117.         boolean flag = false;
  118.         while(true){
  119.             if(temp == null){//已到链表最后
  120.                 break;
  121.             }
  122.             if(temp.next.no == no){
  123.                 //找到待删除节点的前一个节点temp
  124.                 flag =true;
  125.                 break;
  126.             }
  127.             temp = temp.next;
  128.         }
  129.         //判断flag
  130.         if(flag){
  131.             //temp.next = temp.next.next; 单向链表
  132.             temp.pre.next = temp.next;
  133.             //如果这是最后一个节点，就不需要执行下面这句话，否则出现空指针异常。temp.next=null
  134.             if(temp.next != null){
  135.                 temp.next.pre = temp.pre;
  136.             }
  137.         }else{
  138.             System.out.printf("要删除的  %d  节点不存在\n",no);
  139.         }
  140.     }
  142.     //修改链表节点，和单向链表一致
  143.     public void update(HeroNode2 newHeroNode) {
  144.         if (this.head.next == null) {
  145.             System.out.println("链表为空~");
  146.         } else {
  147.             HeroNode2 temp = this.head.next;
  149.             boolean flag;
  150.             for(flag = false; temp != null; temp = temp.next) {
  151.                 if (temp.no == newHeroNode.no) {
  152.                     flag = true;
  153.                     break;
  154.                 }
  155.             }
  157.             if (flag) {
  158.                 temp.name = newHeroNode.name;
  159.                 temp.nickname = newHeroNode.nickname;
  160.             } else {
  161.                 System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  162.             }
  164.         }
  165.     }
  167. }
  171. //定义HeroNode2对象，每个HeroNode对象就是一个节点
  172. class HeroNode2 {
  173.     public int no;
  174.     public String name;
  175.     public String nickname;
  176.     public HeroNode2 next; //指向下一个节点
  177.     public HeroNode2 pre; //指向上一个节点
  178.     //构造器
  179.     public HeroNode2(int no, String name, String nickname) {
  181.         this.no = no;
  182.         this.name = name;
  183.         this.nickname = nickname;
  184.     }
  185.     //为了显示方法，我们重新 toString @Override
  186.     public String toString() {
  187.         return "HeroNode{" +
  188.                 "no=" + no +
  189.                 ", name='" + name + '\'' +
  190.                 ", nickname='" + nickname + '\'' +
  191.                 '}';
  192.     }
  193. }
  197. //作业：双向链表的第二种添加方式：参考单向链表添加方式
  198. //todo

三、单向环形链表

1、单向环形链表图解

image.png

2、Josephu问题

1、Josephu(约瑟夫、约瑟夫环) 问题

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

2、解决方法

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

3、待补充

  1.      <br />      <br />             <br />         <br />