JAVA 数据结构和算法（3）之链表

曾经终败给现在 2022-12-23 03:22 136阅读 0赞

最近学习链表相关知识，写点东西，以备后查，主要从以下几个方面介绍链表 （1）为什么要使用链表 （2）链表简介  （3）单向链表逻辑分析及代码实现（4）双向链表逻辑分析及代码实现（5）单链表常见面试题分析 （6）约瑟夫环实现（7）总结。

(一)为什么要使用链表

数组和链表都是最基础的线性数据结构，可以用来实现栈，队列等非线性，有特定应用场景的数据结构。数组是编程语言提供的很有用的数据结构，但它有两个缺陷，(1)若要改变数组的大小，则需要创建一个新数组，并将原数组中的数据复制到新数组中（2）数组数据的内存依次存储，这意味着要向数组中添加新数据，则需要移动其他数据。换句话来说，**在无序数组中搜索效率低，在有序数组中插入效率又很低，无论哪种情况删除操作效率都很低；而且数组一旦创建，大小不可更改。**这些缺陷可以通过链表来克服，链式结构是存储数据的节点以及指向其他节点的链指针的集合，用这种方法，节点可以定位与内存的任意位置，且从链式结构的一个节点到另一个节点的传递，可以通过结构中存储节点间引用来实现，链式结构最灵活的实现方式是对每个节点使用独立的对象。

（二）链表简介

可以将链表看成有序的列表，**链表**（Linked list）是一种常见的基础数据结构，是一种线性表，顾名思义，是一条相互链接的数据节点表 ，每个节点由两部分组成：数据和指向下一个节点的指针，具有一个数据域和多个指针域的存储单元通常称为节点（node）。

![é¾è¡¨ç»æå¾][20160321211355915]

*  链表的第一个节点和最后一个节点，分别称为链表的头节点和尾节点。尾节点的特征是其 next 引用为空（null）。链表中每个节点的 next 引用都相当于一个指针，指向另一个节点，借助这些 next 引用，我们可以从链表的头节点移动到尾节点。

链表的结构如下图所示，

![è¿éåå¾çæè¿°][SouthEast]

链表通常分为单链表，双向链表，循环链表等。

链表的优缺点为：

> 链表的优点在于：
> 
> 1.  使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。 
> 2.  物理存储单元上非连续，而且采用动态内存分配，能够有效的分配和利用内存资源； 
> 3.  节点删除和插入简单，不需要内存空间的重组。 
> 
> 链表的缺点在于： 
> 
> 1.  不能进行索引访问，只能从头结点开始顺序查找； 
> 2.  数据结构较为复杂，需要大量的指针操作，容易出错。
> 3.  链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

总结：

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

（三）单向链表逻辑分析及代码实现

如果一个节点包含有指向另一个节点的数据域，那么，多个节点可以串联起来，仅通过一个变量访问一个节点，这样的节点序列就是一个链表，其数据结构由节点组成，每个节点保存本节点的数据信息和指向下一个节点的引用。如果节点仅包含有其后继节点的引用，则该链表成为单向链表。

带头结点的单向链表如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70][]

单向链表的存储结构：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 1][]

单链表实现案例：

> 使用带head头的单向链表实现 –水浒英雄排行榜管理
> 
> 1.  完成对英雄人物的增删改查操作， 注: 删除和修改,查找
> 2.  第一种方法在添加英雄时，直接添加到链表的尾部
> 3.  第二种方式在添加英雄时，根据排名将英雄插入到指定位置

单链表逻辑实现分析：

在单链表种实现增加操作：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 3][]

在单链表中实现删除操作：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 4][]

单链表的遍历：

![eb8ada2d82b6629bd8b5f85551840e9e.png][]

单链表的修改：

![20201122160702436.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 5][]

单链表之水浒英雄帮 的代码实现：

package JAVADATASTRTUCRE;
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/18
     * Time: 23:51
     * Description: No Description
     */
    public class SingleLinkedListDemo {
        public static void main(String[] args) {
            //创建节点
            HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
            HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
            HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
            HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
            SingleLinkedList singleLinkedList = new SingleLinkedList();
            //添加
    //        singleLinkedList.add(hero1);
    //        singleLinkedList.add(hero4);
    //        singleLinkedList.add(hero2);
    //        singleLinkedList.add(hero3);
            //添加按照编号
            singleLinkedList.addByOrder(hero1);
            singleLinkedList.addByOrder(hero4);
            singleLinkedList.addByOrder(hero2);
            singleLinkedList.addByOrder(hero3);
    //修改显示
    //        HeroNode heroNode = new HeroNode(1, "宋江", "投降派");
    //        singleLinkedList.update(heroNode);
    //        singleLinkedList.list();
            singleLinkedList.list();
            System.out.println("****************************************");
        singleLinkedList.delete(1);
        singleLinkedList.delete(2);
        singleLinkedList.delete(3);
        singleLinkedList.delete(4);
    
            //遍历
            //singleLinkedList.list();
        }
    }
    
    //定义单链表
    //定义singleLinkedList,管理我们的英雄
    class SingleLinkedList{
        //先定义头节点
        private HeroNode head=new HeroNode(0,"","");
      //添加节点到单链表
        public void add(HeroNode heroNode){
             HeroNode temp =head;
             while(true){
                 //链表的最后
                 if(temp.next==null){
                     break;
                 }
                 temp=temp.next;
             }
          //退出循环时，temp指向链表的最后
             temp.next=heroNode;
        }
        //依顺序添加
        public void addByOrder(HeroNode heroNode){
    
            HeroNode temp =head;
            boolean flag=false;//节点是否存在
            while (true){
                if(temp.next==null){//temp在链表最后
                    break;
                }
                //寻找节点插入位置
            if(temp.next.no>heroNode.no){//位置找到，在temp后面加入
               break;
    
            }else if(temp.next.no==heroNode.no){//编号存在
                flag=true;
                break;
            }
            temp=temp.next;//后移，遍历当前链表
            }
    
            //判断flag；
            if(flag){
                System.out.println("待添加的英雄已经存在，其编号为："+heroNode.no);
            }else{//添加数据到temp的后面
                heroNode.next=temp.next;
                temp.next=heroNode;
            }
        }
    
        //修改节点的信息
        public  void update(HeroNode newHeroNode) {
            //判断链表是否为空
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            //找到要修改的节点
            HeroNode temp = head.next;
              boolean flag=false;//表示是否找到该节点
               while (true){
                   if(temp==null){
                       break;//已经遍历完链表
                   }
                   if(temp.no==newHeroNode.no){
                       flag=true;
                       break;
                   }
                   temp=temp.next;
               }
               //根据flag判断是否修改
            if(flag){
              temp.name=newHeroNode.name;
              temp.nickName=newHeroNode.nickName;
            }else {
                System.out.println("没有找到编号为"+newHeroNode.no+"的英雄");
            }
        }
         //删除节点
          public void delete(int no){
            HeroNode temp=head;
            boolean flag=false;//标志是否找到删除节点
            while(true){
            if(temp.next==null){
                 break;
             }
            if(temp.next.no==no){//找到待删除节点的前一个节点的temp
                flag=true;
                break;
            }
            temp=temp.next;
             if(flag){//删除节点
                 temp.next=temp.next.next;
             }else{
                 System.out.println("节点不存在");
             }
            }
          }
        //遍历
        public  void list(){
            //判断链表是否为空
            if(head.next==null){
                System.out.println("链表为空");
                return;
            }
            HeroNode temp=head.next;
            while(true){
                if(temp==null){
                    break;
                }
                //打印节点、
                System.out.println(temp);
                //temp后移
                temp=temp.next;
            }
        }
    }
    
    
    //定义节点，每个HeroNode对象都是一个节点
    class HeroNode{
        public int no;
        public String name;
        public String nickName;
        public HeroNode next;//指向下一个节点
    
        public HeroNode(int hNo,String hName,String hNickName){
                this.no=hNo;
                this.name=hName;
                this.nickName=hNickName;
        }
        public String toString(){
            return "heroNode [ no="+no+", name=" + name + ", nickname="+nickName+"]";
        }
    
    }

运行结果为：

heroNode [ no=1, name=宋江, nickname=及时雨]
    heroNode [ no=2, name=卢俊义, nickname=玉麒麟]
    heroNode [ no=3, name=吴用, nickname=智多星]
    heroNode [ no=4, name=林冲, nickname=豹子头]
    #######################################
    heroNode [ no=1, name=宋江, nickname=投降派]
    heroNode [ no=2, name=卢俊义, nickname=玉麒麟]
    heroNode [ no=3, name=吴用, nickname=智多星]
    heroNode [ no=4, name=林冲, nickname=豹子头]
    ****************************************
    节点不存在
    heroNode [ no=1, name=宋江, nickname=投降派]
    heroNode [ no=2, name=卢俊义, nickname=玉麒麟]
    heroNode [ no=3, name=吴用, nickname=智多星]
    heroNode [ no=4, name=林冲, nickname=豹子头]
    
    Process finished with exit code 0

单链表的实现二

package DataStrtureDemo;
    
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/19
     * Time: 21:11
     * Description: No Description
     */
    public class IntSLListDemo {
        public static void main(String[] args) {
    
            IntSLList intSLList = new IntSLList();
            intSLList.addToHead(1);
            intSLList.addToHead(2);
            intSLList.addToHead(3);
            intSLList.addToHead(4);
            intSLList.addToHead(5);
            //打印所有
            intSLList.printAll();
    
           //判断是否包含某个元素
            System.out.println(intSLList.isInList(5));
        }
    
    }
    
     class IntSLListNode{
         public int info;
         public IntSLListNode next;
         public IntSLListNode(int i){
             this(i,null);
         }
         public IntSLListNode(int i,IntSLListNode node){
             info=i;
             next=node;
         }
    }
    class  IntSLList{
        protected IntSLListNode head,tail;
        public IntSLList(){
            head=tail=null;
        }
        public boolean isEmpty(){
            return  head==null;
        }
    
        public void addToHead(int el){
           head=new IntSLListNode(el,head);
           if(tail==null){
               tail=head;
           }
        }
    
        public void addToTail(int el){
    
            if(!isEmpty()){//单链表不为空
                tail.next=new IntSLListNode(el);
                tail=tail.next;
            }else {//单链表为空时
                head=tail=new IntSLListNode(el);
            }
        }
    //删除头节点
        public int deleteFromHead(){
            int el=head.info;
            if(head ==tail){
                head=tail=null;
            }else{
                head=head.next;
            }
            return el;
        }
        //删除尾节点
        public int deleteFromTail(){
             int el=tail.info;
             if(head==tail){
                 head=tail=null;
             }else{
               IntSLListNode  tmp;
               for(tmp=head;tmp.next!=tail;tmp=tmp.next);
               tail=tmp;
               tail.next=null;
             }
             return el;
        }
        //打印单链表
        public void printAll(){
             for(IntSLListNode tmp =head;tmp!=null;tmp=tmp.next){
                 System.out.println(tmp.info+"");
             }
        }
        //判断是否在单链表中
        public boolean isInList(int el){
         IntSLListNode tmp;
         for(tmp=head;tmp!=null&&tmp.info!=el;tmp=tmp.next);
         return tmp!=null;
        }
        //删除某个节点
        public void delete(int el){
            if(!isEmpty()){
            if(head==tail&& el==head.info){
             head=tail=null;
            }else if(el==head.info){
                head=head.next;
            }else{
                IntSLListNode pred,tmp;
                for(pred=head,tmp=head.next;tmp!=null&&tmp.info != el;pred=pred.next,tmp=tmp.next){
                    if(tmp!=null){
                        pred.next=tmp.next;
                    }
                    if(tmp==tail){
                        tail=pred;
                    }
                }
              }
            }
        }
    
    }

运行结果为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 6][]

（四）双向链表逻辑分析及代码实现

使用带head头的双向链表实现 –水浒英雄排行榜 管理单向链表的缺点分析:

> 单向链表，查找的方向只能是一个方向，而双向链 表可以向前或者向后查找。
> 
> 单向链表不能自我删除，需要靠辅助节点 ，而双向 链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到temp,temp是待删除节点的前一 个节点、
> 
> 单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，

如果重新定义链表，使其一个节点有两个引用域，一个指向前驱节点，另一个指向后继节点，这样的链表为双向链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5faGFvXzE4MQ_size_16_color_FFFFFF_t_70][]

双向链表的实现的逻辑分析：

删除的实现

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 7][]

双向链表的代码实现：

package JAVADATASTRTUCRE;
    
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/19
     * Time: 4:17
     * Description: No Description
     */
    public class doubleLinkedListDemo {
        public static void main(String[] args) {
            System.out.println("双向链表的测试");
            HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
            HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
            HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
            HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
            //创建双向链表对象
            DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
            doubleLinkedList.add(hero1);
            doubleLinkedList.add(hero2);
            doubleLinkedList.add(hero3);
            doubleLinkedList.add(hero4);
    
    
            doubleLinkedList.list();
            System.out.println("**********");
            HeroNode2 heroNode2 = new HeroNode2(2, "公胜", "入龙");
            doubleLinkedList.update(heroNode2);
           // doubleLinkedList.delete(3);
            doubleLinkedList.list();
    
        }
    }
    
    //创建双向链表的类
    class DoubleLinkedList{
        //初始化
        private HeroNode2 head=new HeroNode2(0,"","");
        //返回头节点
        public HeroNode2 getHead(){
            return head;
        }
    
        public void add(HeroNode2 heroNode){
            HeroNode2 temp =head;
            while(true){
                //链表的最后
                if(temp.next==null){
                    break;
                }
                temp=temp.next;
            }
            //退出循环时，temp指向链表的最后,
            //形成一个双向链表
            temp.next=heroNode;
            heroNode.pre=temp;
        }
    
        //删除一个节点
        //删除节点，双向链表，直接找到删除节点，自我删除
        public void delete(int no){
    
            if(head.next==null){
                System.out.println("链表为空，无法删除");
            }
    
            HeroNode2 temp=head.next;
            boolean flag=false;//标志是否找到删除节点
            while(true){
                if(temp==null){//已经找到链表最后节点的next
                    break;
                }
                if(temp.no==no){//找到待删除节点的前一个节点的temp
                    flag=true;
                    break;
                }
                temp=temp.next;
                if(flag){//删除节点
                    temp.pre.next=temp.next;
                    //注意：最后一个节点不能执行下面这句话，否则
                    //出现空指针异常
                    if(temp.next!=null) {
                        temp.next.pre = temp.pre;
                    }
                }else{
                    System.out.println("节点不存在");
                }
            }
    
        }
    
    
    //修改一个结点的内容
    //修改节点的信息
    public  void update(HeroNode2 newHeroNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //找到要修改的节点
        HeroNode2 temp = head.next;
        boolean flag=false;//表示是否找到该节点
        while (true){
            if(temp==null){
                break;//已经遍历完链表
            }
            if(temp.no==newHeroNode.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        //根据flag判断是否修改
        if(flag){
            temp.name=newHeroNode.name;
            temp.nickName=newHeroNode.nickName;
        }else {
            System.out.println("没有找到编号为"+newHeroNode.no+"的英雄");
        }
    
      }
    
        //遍历
        public  void list(){
            //判断链表是否为空
            if(head.next==null){
                System.out.println("链表为空");
                return;
            }
            HeroNode2 temp=head.next;
            while(true){
                if(temp==null){
                    break;
                }
                //打印节点、
                System.out.println(temp);
                //temp后移
                temp=temp.next;
            }
        }
    }
    
    //定义节点，每个HeroNode对象都是一个节点
    class HeroNode2{
        public int no;
        public String name;
        public String nickName;
        public HeroNode2 next;//指向下一个节点，默认为null
       public HeroNode2 pre;//指向前一个节点，默认为null
        public HeroNode2(int hNo,String hName,String hNickName){
            this.no=hNo;
            this.name=hName;
            this.nickName=hNickName;
    
        }
        public String toString(){
            return "heroNode [ no="+no+", name=" + name + ", nickname="+nickName+"]";
        }
    }

运行结果为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 8][]

（五）单向链表常见面试题

> 单链表的常见面试题有如下:
> 
> 1.  求单链表中有效节点的个数 查找单链表中的倒数第k个结点
> 2.  单链表的反转
> 3.  从尾到头打印单链表 【要求方式1：反向遍历 。 方式2：Stack栈】

2.单链表的反转逻辑分析

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 10][]

3.逆序打印单链表的逻辑分析

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 11][]

package JAVADATASTRTUCRE;
    
    import java.util.Stack;
    
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/19
     * Time: 1:44
     * Description: No Description
     */
     class testSingleLinkedListDemo {
        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, "林冲", "豹子头");
            testSingleLinkedList testSingleLinkedList = new testSingleLinkedList();
            //添加
            //singleLinkedList.add(hero1);
            //singleLinkedList.add(hero4);
            //singleLinkedList.add(hero2);
            //singleLinkedList.add(hero3);
            //添加按照编号
             testSingleLinkedList.addByOrder(hero1);
             testSingleLinkedList.addByOrder(hero4);
             testSingleLinkedList.addByOrder(hero2);
            testSingleLinkedList.addByOrder(hero3);
    //修改显示
    //        HeroNode heroNode = new HeroNode(1, "宋江", "投降派");
    //        singleLinkedList.update(heroNode);
    //        singleLinkedList.list();
             testSingleLinkedList.list();
            System.out.println("****************************************");
    //        singleLinkedList.delete(1);
    //        singleLinkedList.delete(2);
    //        singleLinkedList.delete(3);
    //        singleLinkedList.delete(4);
            //遍历
            //singleLinkedList.list();
            // System.out.println(getLength(testSingleLinkedList.getHead()));
            HeroNode res =finalLastIndexNode(testSingleLinkedList.getHead(),2);
           System.out.println("res="+res);
    
         //单链表的反转
            System.out.println("反转单链表");
            reverselist(testSingleLinkedList.getHead());
            testSingleLinkedList.list();
    
            System.out.println("***********************");
             reversePrint(testSingleLinkedList.getHead());
    
    
        }
    
        //获取单链表有效节点的个数（若带头节点，不需要统计）
        /*
        @param head 链表头节点
        @return 返回的是有效节点的个数
         */
    
        public static int getLength(HeroNode head) {
            if (head.next == null) {
                return 0;
            }
            int length = 0;
            HeroNode cru = head.next;
            while (cru != null) {
                length++;
                cru = cru.next;
            }
            return length;
        }
    
       //查找单链表倒数第k各节点
         public static HeroNode finalLastIndexNode(HeroNode head,int index){
            if(head.next==null){
                return null;
            }
            int size=getLength(head);
            if(index<=0||index>size){
                return null;
            }
            HeroNode   cru=head.next;
    
             for (int i=0;i<size-index;i++){
               cru=cru.next;
             }
             return cru;
    
    
    
         }
    
        //单链表反转
         public static void reverselist(HeroNode head){
            //若当前链表为空或只有一个节点，无需反转
            if(head.next==null||head.next.next==null){
                return;
            }
    
            //定义一个辅助指针（遍历原来的链表）
           HeroNode cur=head.next;//当前节点
           HeroNode next =null;//指向当前节点cur的下一个节点
           HeroNode reverseHead=new HeroNode(0,"","");
           //遍历原来的链表，每边历一个节点，将其取出，把那个放在reverseHead的最前端
          while(cur!=null){
              next=cur.next;//保存当前节点的下一个节点
              cur.next=reverseHead.next;//将cur的下一个节点指向链表的最前端
             reverseHead.next=cur;
              cur=next;//cur后移，指向下一个节点
          }
          //将head。next指向reverseHead.next
        head.next=reverseHead.next;
    
    
    
    
        }
    
        //利用栈来逆序打印单链表
    
        public static void reversePrint(HeroNode head){
            if(head.next==null){
                return;//空链表，无法打印
            }
            Stack<HeroNode> heroNodestack = new Stack<HeroNode>();
            HeroNode cur=head.next;
            while (cur!=null){
                heroNodestack.push(cur);
                cur=cur.next;//cur后移，指向写一个节点
            }
    
            //将栈中的数据打印
            while (heroNodestack.size()>0){
                System.out.println(heroNodestack.pop());
            }
    
        }
    
    
    
    }
    
    //定义单链表
    //定义singleLinkedList,管理我们的英雄
    class testSingleLinkedList{
        //先定义头节点
        private HeroNode head=new HeroNode(0,"","");
      //返回头节点
        public HeroNode getHead(){
            return head;
        }
        //添加节点到单链表
        public void add(HeroNode heroNode){
            HeroNode temp =head;
            while(true){
                //链表的最后
                if(temp.next==null){
                    break;
                }
                temp=temp.next;
            }
            //退出循环时，temp指向链表的最后
            temp.next=heroNode;
        }
        //依顺序添加
        public void addByOrder(HeroNode heroNode){
    
            HeroNode temp =head;
            boolean flag=false;//节点是否存在
            while (true){
                if(temp.next==null){//temp在链表最后
                    break;
                }
                //寻找节点插入位置
                if(temp.next.no>heroNode.no){//位置找到，在temp后面加入
                    break;
    
                }else if(temp.next.no==heroNode.no){//编号存在
                    flag=true;
                    break;
                }
                temp=temp.next;//后移，遍历当前链表
            }
    
            //判断flag；
            if(flag){
                System.out.println("待添加的英雄已经存在，其编号为："+heroNode.no);
            }else{//添加数据到temp的后面
                heroNode.next=temp.next;
                temp.next=heroNode;
            }
        }
    
        //修改节点的信息
        public  void update(HeroNode newHeroNode) {
            //判断链表是否为空
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            //找到要修改的节点
            HeroNode temp = head.next;
            boolean flag=false;//表示是否找到该节点
            while (true){
                if(temp==null){
                    break;//已经遍历完链表
                }
                if(temp.no==newHeroNode.no){
                    flag=true;
                    break;
                }
                temp=temp.next;
            }
            //根据flag判断是否修改
            if(flag){
                temp.name=newHeroNode.name;
                temp.nickName=newHeroNode.nickName;
            }else {
                System.out.println("没有找到编号为"+newHeroNode.no+"的英雄");
            }
    
        }
        //删除节点
        public void delete(int no){
            HeroNode temp=head;
            boolean flag=false;//标志是否找到删除节点
            while(true){
                if(temp.next==null){
                    break;
                }
                if(temp.next.no==no){//找到待删除节点的前一个节点的temp
                    flag=true;
                    break;
                }
                temp=temp.next;
                if(flag){//删除节点
                    temp.next=temp.next.next;
                }else{
                    System.out.println("节点不存在");
                }
            }
    
        }
        //遍历
        public  void list(){
            //判断链表是否为空
            if(head.next==null){
                System.out.println("链表为空");
                return;
            }
            HeroNode temp=head.next;
            while(true){
                if(temp==null){
                    break;
                }
                //打印节点、
                System.out.println(temp);
                //temp后移
                temp=temp.next;
            }
        }
    }
    
    
    //定义节点，每个HeroNode对象都是一个节点
    class testHeroNode{
        public int no;
        public String name;
        public String nickName;
        public HeroNode next;//指向下一个节点
    
        public testHeroNode(int hNo,String hName,String hNickName){
            this.no=hNo;
            this.name=hName;
            this.nickName=hNickName;
        }
        public String toString(){
            return "heroNode [ no="+no+", name=" + name + ", nickname="+nickName+"]";
        }
    
    }

运行结果为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 12][]

（六）约瑟夫环实现

问题描述：

> Josephu(约瑟夫、约瑟夫环)  问题 Josephu  问题为：
> 
> 设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
> 
> 提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

![20201122173710125.png][]

逻辑分析：

Josephu  问题为：

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

n = 5 , 即有5个人 k = 1, 从第一个人开始报数 m = 2, 数2下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 13][]

> 构建一个单向的环形链表思路
> 
> 1.   先创建第一个节点, 让 first 指向该节点，并形成环形
> 2.  后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.
> 
> 遍历环形链表
> 
> 1.  先让一个辅助指针(变量) curBoy，指向first节点
> 2.   然后通过一个while循环遍历 该环形链表即可 curBoy.next  == first 结束

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 14][]

代码实现：

package JAVADATASTRTUCRE;
    
    
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/19
     * Time: 15:01
     * Description: No Description
     */
    public class Jusepfu {
        public static void main(String[] args) {
            CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
            circleSingleLinkedList.addBoy(5);
            circleSingleLinkedList.showBoy();
            System.out.println("******************************");
         //测试出圈
            circleSingleLinkedList.countBoy(1,2,5);
    
        }
        
    }
    
    //创建环形单项链表
    class CircleSingleLinkedList{
        //创建First节点，
        private Boy first =new Boy(-1);
         //添加小孩节点，构成一个环形链表
        public void  addBoy(int nums) {
            //nums数据校验
            if (nums < 1) {
                System.out.println("nums值不正确");
                return;
            }
            Boy curBoy = null;
            //利用for循环创建环形链表
            for (int i = 1; i < nums+1; i++) {
                //根据编号创建小孩节点
                Boy boy = new Boy(i);
                //第一个小孩
                if (i == 1) {
                    first = boy;
                    first.setNext(first);
                    curBoy = first;
                } else {
                    curBoy.setNext(boy);
                    boy.setNext(first);
                    curBoy = boy;
                }
            }
        }
         ///遍历所有节点
           public void showBoy(){
               if(first==null){//链表为空
                   System.out.println("没有数据");
                   return;
               }
               Boy curBoy=first;
               while (true){
                   System.out.println("小孩的编号为"+curBoy.getNo());
                   if(curBoy.getNext()==first){
                       break;
                   }
                   curBoy=curBoy.getNext();//curBoy后移
    
            }
    
        }
    
        //根据用户的输入，计算小孩出圈的顺序
        /*
    
        @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;
          //需要创建辅助变量，事先指向环形链表的最后一个节点
          while (true){
              if(helper.getNext()==first){//helper指向最后
                  break;
              }
              helper=helper.getNext();
          }
          //小孩报数前，first和helper移动k-1次
          for(int j=0;j<startNO-1;j++){
             first=first.getNext();
             helper=helper.getNext();
          }
         //小孩移动时，helper和first同时移动m-1次，然后出圈
          while (true){
              if (helper==first){//圈中只有一个人
                  break;
              }
    
          //让first和helper同时移动countnum-1
            for(int j=0;j<countNum-1;j++){
                first=first.getNext();
                helper=helper.getNext();
            }
           //此时first指向出圈小孩
            System.out.println("小孩出圈id为"+first.getNo());
            first=first.getNext();
            helper.setNext(first);
        }
          System.out.println("最后在圈内的小孩的编号为"+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;
    }
    }

运行结果为：

小孩的编号为1
    小孩的编号为2
    小孩的编号为3
    小孩的编号为4
    小孩的编号为5
    ******************************
    小孩出圈id为2
    小孩出圈id为4
    小孩出圈id为1
    小孩出圈id为5
    最后在圈内的小孩的编号为3
    
    Process finished with exit code 0

（七）总结

链表相比较数组，增加了下一个节点的位置，包括前驱节点和后继节点，每个链表都包括一个LinikedList对象和许多Node对象，只有下一个节点的引用称为单向链表，两个都有的称为双向链表。next值为null则说明是链表的结尾，如果想找到某个节点，我们必须从第一个节点开始遍历，不断通过next找到下一个节点，直到找到所需要的。

[20160321211355915]: /images/20221120/1957f3e5baaa4033a4eea3c2c7b182b2.png
[SouthEast]: /images/20221120/785f8fefbcf54832a23644106173c6e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70]: /images/20221120/9d92db9958ce420791f0a7ad191028a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201122154043183.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201122160136898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201122160346506.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201122160430805.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[eb8ada2d82b6629bd8b5f85551840e9e.png]: https://img-blog.csdnimg.cn/img_convert/eb8ada2d82b6629bd8b5f85551840e9e.png
[20201122160702436.png]: https://img-blog.csdnimg.cn/20201122160702436.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201122160643509.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201122162303389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5faGFvXzE4MQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301112739934.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5faGFvXzE4MQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2020112217253713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201122172834381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20201122173233165.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020112217330123.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20201122173058523.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20201122173548338.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[20201122173710125.png]: https://img-blog.csdnimg.cn/20201122173710125.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20201122173922743.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20201122174041634.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70