链表

链表

单链表介绍和内存分布

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

单链表的创建和遍历

带头节点的单链表

1. head节点 不存放具体数据，作用是表示单链表的头

2. 单链表的最后一个节点next域指向为NULL

3. 单链表的创建

   1. 先创建一个head头节点
   2. 后面我们每添加一个节点，就直接加入到链表的最后

4. 遍历

   1. 通过一个辅助遍历，帮助遍历整个链表

5. 单链表的代码实现

   package sparsearray;
   
   public class SingleLinkedList {
       public static void main(String[] args) {
           //进行测试
           //先创建节点
           Heronode heronode1 =new Heronode(1, "宋江", "及时雨");
           Heronode heronode2 =new Heronode(2, "卢俊义", "玉麒麟");
           Heronode heronode3 =new Heronode(3, "吴用", "智多星");
           Heronode heronode4=new Heronode(4, "林冲", "豹子头");
   
           //创建链表
           SingleLinked singleLinked = new SingleLinked();
           singleLinked.add(heronode1);
           singleLinked.add(heronode2);
           singleLinked.add(heronode3);
           singleLinked.add(heronode4);
   
           singleLinked.list();
   
           singleLinked.addByOrder(heronode2);
           singleLinked.addByOrder(heronode1);
           singleLinked.addByOrder(heronode3);
           singleLinked.addByOrder(heronode4);
   
           singleLinked.list();
   
       }
   }
   
   //定义一个类用来管理节点
   class SingleLinked{
   
       //初始化一个头节点，头节点不能动，不存放具体数据
       private Heronode head=new Heronode(0, "", "");
   
       /*
       添加节点到单链表
       当不考虑编号顺序时
       1.找到当前链表的最后一个节点
       2.将最后这个节点的next 指向新的节点
        */
   
       public void add(Heronode heronode){
   
           //定义一个temp辅助遍历
           Heronode temp = head;
           //遍历链表，找到最后
           while (true){
               if (temp.next==null){
                   break;
               }
               //没有找到最后，就将temp后移
               temp=temp.next;
           }
           //将最后一个节点的next 指向新的节点
           temp.next=heronode;
       }
   
   
       //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
       //如果前面有这个排名，则添加失败，并给出提示
       public void addByOrder(Heronode heronode){
   
           Heronode temp =head;
           boolean flag = false;
           while (true){
               if (temp.next==null){
                   break;
               }
               if (temp.next.no>heronode.no){
                   break;
               }
               else  if (temp.next.no==heronode.no){
                   flag =true;
                   break;
               }
               temp =temp.next;
           }
           if (flag){
               System.out.println("添加的排名重复");
           }else{
               temp.next=heronode;
               heronode.next=temp.next;
           }
       }
   
       //显示链表
       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.toString());
               //将temp后移
               temp =temp.next;
           }
       }
   }
   
   //定义HeroNode,每个HeroNode对象是一个节点
   class Heronode{
       public int no;
       public String name;
       public String nickname;
       public  Heronode next;//指向下一个节点
   
       //构造器
       public Heronode(int hNo,String hName, String hNickname){
           no=hNo;
           name=hName;
           nickname=hNickname;
       }
   
       public String toString() {
           return "Heronode{" +
                   "no=" + no +
                   ", name='" + name + '\'' +
                   ", nickname='" + nickname;
       }
   }

6. 从单链表中删除节点

   • 我们先找到需要删除的节点的前一个节点
   • temp.next =temp.next.next

单链表面试题（新浪、百度、腾讯）

获取单链表中节点的个数（如果是带头节点的链表，不统计头节点）

public static  int getLength(Heronode head){
       if (head.next==null){
           return 0;
       }
       int length = 0;
       Heronode cur =head.next;//这里没有统计头节点
       while (cur != null){
           length++;
           cur = cur.next;//遍历
       }
       return  length;
   }

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

/*
  思路
  1.编写一个方法，接收head节点，同时接收一个index
  2.index 表示是倒数第index节点
  3.先把链表从头到尾遍历，得到链表的总的长度getlength
  4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
   */
  public  static Heronode findeLastIndexNode(Heronode head,int index){
      if (head.next == null){
          return  null;
      }
      int size =getLength(head);//链表的长度
      if (index <= 0 || index > size){
          return  null;
      }
      Heronode temp =head.next;
      //for循环定位到index
      for (int i =0; i <size-index ; i++) {
          temp=temp.next;
      }
      return  temp;
  }

单链表的反转[腾讯面试题]

//将单链表反转
 public  static  void  reversetLsit(Heronode head){
     //判断当前链表是否为空，或者只有一个节点
     if (head.next==null || head.next.next == null){
         return;
     }
     //定义一个辅助的指针
     Heronode cur = head.next;
     Heronode next = null;
     Heronode reverseHead = new Heronode(0, "", "");
     while (cur !=null){
         next=cur.next;
         reverseHead.next=cur;
         cur.next=reverseHead.next;
         cur=next;//让cur后移
     }
     //将head.next 指向reversehead.next 实现单链表的反转
     head.next = reverseHead.next;
 }

双向链表

• 分析双向链表的遍历，添加，修改，删除的操作思路

  1. 遍历方法和单链表一样，只是可以向前，也可以向后查找
  2. 添加（默认添加到双向链表的最后）
     1. 先找到双向链表的最后这个节点
     2. temp.next=newHeroNode
     3. newHeroNode.pre=temp
  3. 修改 同单向链表
  4. 删除
     1. 因为是双向链表，可以实现自我删除某个节点
     2. 直接找到要删除的这个节点，比如temp
     3. temp.pre =temp.next
     4. temp.next.pre=temp.pre;

• 双向链表的代码实现

  package sparsearray;
  
  public class DoubleLinked {
      public static void main(String[] args) {
          //进行测试
          //先创建节点
          Hero heronode1 =new Hero(1, "宋江", "及时雨");
          Hero heronode2 =new Hero(2, "卢俊义", "玉麒麟");
          Hero heronode3 =new Hero(3, "吴用", "智多星");
          Hero heronode4=new Hero(4, "林冲", "豹子头");
  
          //创建链表
  
          DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
  
          doubleLinkedList.add(heronode1);
          doubleLinkedList.add(heronode2);
          doubleLinkedList.add(heronode3);
          doubleLinkedList.add(heronode4);
          doubleLinkedList.list();
  
          //修改
          Hero newHexo = new Hero(4, "公孙胜", "入云龙");
          doubleLinkedList.update(newHexo);
          doubleLinkedList.list();
  
  
          //删除
          doubleLinkedList.del(3);
          doubleLinkedList.list();
  
  
      }
  }
  class DoubleLinkedList{
  
      //初始化头节点
      private  Hero head = new Hero(0, "","");
  
      //返回头节点
      public  Hero getHead(){
          return head;
      }
  
      //遍历双向链表
      public  void list(){
          //判断链表是否为空
          if (head.next==null){
              System.out.println("链表为空");
              return;
          }
          //因为头节点不能动，我们需要一个辅助变量来遍历
          Hero temp = head.next;
          while (true){
              if (temp==null){
                  break;
              }
              System.out.println(temp.toString());
              //将temp后移
              temp =temp.next;
          }
      }
  
      //添加双向链表
  
      public void add(Hero hero){
  
          //定义一个temp辅助遍历
          Hero temp = head;
          //遍历链表，找到最后
          while (true){
              if (temp.next==null){
                  break;
              }
              //没有找到最后，就将temp后移
              temp=temp.next;
          }
          //将最后一个节点的next 指向新的节点
          temp.next=hero;
          hero.pre=temp;
      }
  
      //修改双向链表
      public void update(Hero hero){
  
          //判断是否为空
          if (head.next == null){
              System.out.println("链表为空");
              return;
          }
  
          Hero temp =head.next;
          boolean flag = false;
          while (true){
              if (temp == null){
                  break;
              }
              if (temp.no == hero.no){
                  flag = true;
                  break;
              }
              temp = temp.next;
          }
          if (flag){
              temp.name = hero.name;
              temp.nickname =hero.nickname;
          }else {
              System.out.println("信息有误");
          }
      }
  
      //删除节点
      public void del(int no){
          Hero temp =head.next;
          boolean flag = false;
          while (true){
              if (temp==null){
                  break;
              }
              if (temp.no == no){
                  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("删除的节点不存在");
          }
  
      }
  
  
  
  }
  class Hero{
      public int no;
      public String name;
      public String nickname;
      public Hero next;//指向下一个节点
      public Hero pre;//指向前一个节点
  
      //构造器
      public Hero(int no, String name, String nickname) {
          this.no = no;
          this.name = name;
          this.nickname = nickname;
      }
  
      @Override
      public String toString() {
          return "Hero{" +
                  "no=" + no +
                  ", name='" + name + '\'' +
                  ", nickname='" + nickname + '\'';
      }
  }

单向环形链表

约瑟夫问题（约瑟夫环）

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

约瑟夫问题的代码实现

1. 构建一个单向环形链表思路

   1. ，先创建第一个节点，让first指向该节点，并形成环形
   2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。

2. 遍历环形链表

   1. 先让一个辅助指针（变量）temp，指向first节点
   2. 然后通过一个while循环遍历该环形链表即可 temp.next =first 结束

3. 约瑟夫问题出队列

   1. 需要创建一个辅助指针helper，事先指向环形链表的最后节点

   2. 当小孩报数时，让first和辅助指针同时移动m-1次

   3. 这时候将first指向的小孩节点出圈

      first =first.next

      helper.next=first

      package sparsearray;
      
      public class Josefu {
          public static void main(String[] args) {
      
              CircleSingleLinkedlist circleSingleLinkedlist = new CircleSingleLinkedlist();
              circleSingleLinkedlist.addBoy(5);//加入五个小孩节点
              circleSingleLinkedlist.showBoy();
      
              circleSingleLinkedlist.countBoy(1, 2, 5);
          }
      }
      //创建环形单向链表
      class CircleSingleLinkedlist {
      
          //创建一个first节点，当前没有编号
          private Boy first = null;
      
          //添加小孩节点，构建成一个环形的链表
          public void addBoy(int nums) {
              if (nums < 1) {
                  System.out.println("nums的值不争取");
                  return;
              }
              Boy curBoy = null;//辅助指针，帮助构建环形链表
              //使用for循环来创建环形链表
              for (int i = 1; i <= nums; 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;
              }
              //first,不能动 使用辅助指针
              Boy curBoy = first;
              while (true) {
                  System.out.printf("编号是%d\n", curBoy.getNo());
                  if (curBoy.getNext() == first) {//说明已经编列完毕
                      break;
                  }
                  curBoy = curBoy.getNext();//指针后移
              }
          }
      
      
          //根据用户的输入，计算出小孩出圈的顺序
          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){
                      break;
                  }
                  helper=helper.getNext();
              }
              //报数前，先让first和helper移动k-1次
              for (int i = 0; i <startNo-1 ; i++) {
                  first = first.getNext();
                  helper = helper.getNext();
              }
              //当小孩报数时，让first和helper指针同时移动m-1次，然后出圈
              //这里是一个循环操作
              while (true) {
                  if (helper == first) {//说明圈中只有一个节点
                      break;
                  }
                  //让first和helper指针同时的移动countNum -1
                  for (int i = 0; i <countNum-1 ; i++) {
                      first=first.getNext();
                      helper=helper.getNext();
                  }
                  //这时first指向的小孩节点出圈
                  System.out.println(first.getNo());
                  first=first.getNext();
                  helper.setNext(first);
              }
              System.out.println("最后留的"+first.getNo());
      
          }
      }
      
      
      class Boy{
          private  int no;
          private Boy next;//指向下一个节点
      
          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;
          }
      }