单链表常见面试题

public class Test{
    /**
     * 获取单链表的有效节点的个数，不包括头节点
     * @param head 链表的头节点
     * @return 返回的是有效节点的个数
     */
    public static int getLength(HeroNode head){
        if(head.next == null){ // 空链表
            return 0;
        }
        int length = 0; //定义一个辅助的变量，从head.next开始统计，不统计头节点
        HeroNode cur = head.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return  length;
    }
}

public class Test{
    /**
     * 查找单链表中的倒数第k个节点
     * 1. 通过遍历，得到链表的总长度
     * 2. 得到长度后，链表的第size - index个，就是倒数第index个节点
     * 3. 通过遍历获得size - index 节点，如果有返回节点，否则返回null
     * @param head 头节点
     * @param index 倒数第index个节点
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        if(head.next == null){
            return null; // 判断链表是否空，是返回null
        }
        int size = getLength(head);
        if(index <= 0 || index > size){
            return null; // 判断index是否小于0 或者 大于节点的个数，小于0或大于size返回null
        }
        HeroNode cur = head.next; // 定义辅助变量，通过辅助变量遍历链表，得到size - index，即倒数index
        for(int i = 0; i < size - index;i++){
            cur = cur.next;
        }
        return cur;
    }
}

public class Test{
    /**
     *  将单链表反转
     * @param head
     */
    public static void reverseList(HeroNode head){
        if(head.next == null || head.next.next == null){ // 链表为空，或只有1个节点，直接返回
            return;
        }

        HeroNode cur = head.next; // 定义一个变量，用来遍历
        HeroNode next = null; // 保存当前节点的下一个节点
        HeroNode reverseHead = new HeroNode(0,"",""); // 创建一个新的链表

        while (cur != null){
            next = cur.next; // 暂时保存当前节点的下一个节点
            cur.next = reverseHead.next; // 将当前节点的下一个节点链接到新链表中最前面的节点
            reverseHead.next = cur; // 将当前节点链接到新链表
            cur = next; // cur后移
        }
        head.next = reverseHead.next; // 将head.next指向reverseHead.next，实现反转
    }
}

public class Test{
    /**
     * 利用栈先进后出的特点，实现逆序打印的效果
     * @param head
     */
    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()); // 出栈并打印
        }
    }
}