单链表

发表于 更新于 分类于

单链表（其三）

单向链表的练习

背景

  • 数据结构——单向链表

  • 博主以b站尚硅谷Java数据结构与算法课进行学习

问题（一）

  • 获得单链表的节点的个数，不需要统计头节点

解决步骤

  • 判断链表是否为空，是的话返回0

  • 设置辅助变量cur指向head.next

  • 设置length计算节点个数

    • 代码实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      //获得单链表的节点的个数，不需要统计头节点
         public static int getLength(HeroNode head){
             if(head.next == null){//判断是否为空列表，是的话返回0
                 return 0;
             }
             HeroNode cur = head.next;//辅助变量cur
             int length = 0;//计算节点个数
             while(cur != null){//若cur等于null，则代表到达单链表尾部
                 length++;
                 cur=cur.next;//遍历
             }
             return length;
         }

问题（二）

  • 查找单链表中倒数第k个节点

解决步骤

  • 编写一个方法，接收head节点，同时接收一个index

  • index表示是倒数地index个节点

  • 先把链表从头遍历到尾，得到链表的总长度

  • 得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到

    • 代码实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      //查找单链表中倒数第k个节点
       //1.编写一个方法，接收head节点，同时接收一个index
       //2.index表示是倒数地index个节点
       //3.先把链表从头遍历到尾，得到链表的总长度
       //4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
       public static HeroNode findLastIndexNode(HeroNode head,int index){
           if(head.next == null ){//判断链表是否为空
               return null;
           }
           int size = getLength(head);//调用getLength方法得到链表长度
           if(index<=0||index>size){  //如果要查找的数小于0或者大于链表长度，则返回空
               return null;
           }
           HeroNode cur = head.next;
           for(int i=0;i<size-index;i++){
               cur = cur.next;
           }
           return cur;
       }

问题（三）

  • 将单链表反转

解决步骤

  • 先定义一个新节点reverseHead = new HeroNode

  • 从头到尾遍历原来的链表，每遍历一个节点就将它取出，放在新链表的最前端

  • 从原来的链表的head.next=reverseHead.next

  • head节点

    • 不存放具体数据
    • 作用就是表示单链表头的next

  • reversHead节点

    • 不存放具体数据
    • 作用就是表示单链表头的next

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    //单链表的反转
    //1.先定义一个新节点reverseHead = new HeroNode
    //2.从头到尾遍历原来的链表，每遍历一个节点就将它取出，放在新链表的最前端
    //3.从原来的链表的head.next=reverseHead.next
    //head节点
    //1.不存放具体数据
    //2.作用就是表示单链表头的next
    //reversHead节点
    //1.不存放具体数据
    //2.作用就是表示单链表头的next
    public static void reversetList(HeroNode head){
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null||head.next.next == null){
            System.out.println("链表为空");
            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加到新的链表上
            cur = next;//让cur后移
        }
        //将head.next指向reverHead.next,实现单链表的反转
        head.next = reverseHead.next;
    }

问题（四）

  • 从尾到头打印单链表

解决步骤

  • 方法一：逆序打印单链表，这样的问题：会破坏当前链表，不建议

  • 方法二：可以利用栈这个数据结构，将各个节点压入栈中，利用栈的先进后出的特点，实现逆序打印

  • 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //从尾到头打印单链表
      //思路：1.逆序打印单链表，这样的问题：会破坏当前链表，不建议
      //     2.可以利用栈这个数据结构，将各个节点压入栈中，利用栈的先进后出的特点，实现逆序打印
     public static void reversePrint(HeroNode head){
         //如果当前链表为空
         if(head.next == null){
             return;
         }
         Stack<HeroNode> stack = new Stack<>();//创建一个栈，将各个节点压入栈中
         HeroNode cur = head.next;
         while(cur!=null){
             stack.push(cur);
             cur= cur.next;
         }
         while(stack.size()>0){
             System.out.println(stack.pop());//出栈打印，栈的特点是先进后出
         }
     }