• 求单链表中有效节点的个数
    • 查找单链表中的倒数第k个结点 【新浪面试题】
    • 单链表的反转【腾讯面试题，有点难度】
    • 从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
    • 合并两个有序的单链表，合并之后的链表依然有序【课后练习.】

    直接看老师代码演示。

    哔哩哔哩动画

    1.     //方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
    2.     /**
    3.      *
    4.      * @param head 链表的头节点
    5.      * @return 返回的就是有效节点的个数
    6.      */
    7.     public static int getLength(HeroNode head) {
    8.         if(head.next == null) { //空链表
    9.             return 0;
    10.         }
    11.         int length = 0;
    12.         //定义一个辅助的变量, 这里我们没有统计头节点
    13.         HeroNode cur = head.next;
    14.         while(cur != null) {
    15.             length++;
    16.             cur = cur.next; //遍历
    17.         }
    18.         return length;
    19.     }

    img

    2.     //查找单链表中的倒数第k个结点 【新浪面试题】
    3.     //思路
    4.     //1. 编写一个方法，接收head节点，同时接收一个index
    5.     //2. index 表示是倒数第index个节点
    6.     // 音为我们这个是单链表,不可能从后面往前走
    7.     //3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
    8.     //4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
    9.     //5. 如果找到了，则返回该节点，否则返回nulll
    10.     public static HeroNode findLastIndexNode(HeroNode head, int index) {
    11.         //判断如果链表为空，返回null
    12.         if(head.next == null) {
    13.             return null;//没有找到
    14.         }
    15.         //第一个遍历得到链表的长度(节点个数)
    16.         int size = getLength(head);
    17.         //第二次遍历  size-index 位置，就是我们倒数的第K个节点
    18.         //先做一个index的校验
    19.         if(index <=0 || index > size) {
    20.             return null;
    21.         }
    22.         //定义给辅助变量， for 循环定位到倒数的index
    23.         HeroNode cur = head.next; //3 // 3 - 1 = 2
    24.         for(int i =0; i< size - index; i++) {
    25.             cur = cur.next;
    26.         }
    27.         return cur;
    29.     }