单链表面试题

单链表的面试题

• 1.求单链表中的有效节点的个数

 /**
     *
     * @param heroNode  链表的头结点
     * @return 返回的就是有效节点的个数
     */
    public static int getLength(HeroNode heroNode){
        if (heroNode.next == null){
            return 0;
        }
        int length = 0;
        HeroNode temp = heroNode.next;
        while (temp != null){
            length++;
            temp = temp.next; //遍历整个链表
        }
        
        return length;
    }

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

 /**
     * 查找单链表中的倒数第k个节点
     * @param index
     * @param heroNode
     * @return
     */
    public  static HeroNode getNodeByInedx(int index,HeroNode heroNode){
        if (heroNode.next == null){
            return  null;
        }
        int size = getLength(heroNode);
        //第二次遍历
        if(index < 0 || index >= size){
            return  null;
        }
        HeroNode temp = heroNode.next;
        for (int i = 0; i < size-index; i++) {
            temp = temp.next;
        }

        return temp;
    }

• 3.单链表的反转

   /**
     * 链表反转
     * @param head
     */
    public static  void reverseSingleLinkedList(HeroNode head){
        if (head == null || head.next.next == null) {
            return;
        }
        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reversHead = new HeroNode(0,"","");
        while (cur.next !=null){
            next = cur.next;
            cur.next = reversHead.next;
            cur = next;//后移

        }
        
        head.next  = reversHead.next ;
    }

• 从头到尾打印链表

 /**
     * 逆序打印链表
     * @param head
     */
    public static void reversPrint(HeroNode head){
        if (head == null ) {
            return;
        }
        Stack<HeroNode> heroNodes = new Stack<>();
        HeroNode temp = head.next;
        while (temp != null){
            heroNodes.push(temp);
            temp = temp.next;
        }
       while (heroNodes.size()>0){
           System.out.println(heroNodes.pop());
       }
    }