Java教程

Java数据结构和算法(单链表的面试题)

本文主要是介绍Java数据结构和算法(单链表的面试题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1、求单链表有效节点的个数。

//问:求单链表有效节点的个数。
//方法:如果是带头节点的链表,需求不统计头节点

    /**
     *
     * @param head 链表的头节点
     * @return 返回的是有效节点的个数
     */
    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;
}

 2、查找单链表中的倒数第k个节点(新浪面试题)

 

//问:查找单链表中的倒数第k个节点(新浪面试题)
    //思路:
    //1、编写一个方法,接受一个head节点,同时接受一个index
    //2、index表示的是倒数第index个节点
    //3、先把链表从头到位遍历一下得到链表的总的长度,调用上方,getLength
    //4、得到size后,我们从链表的第一个开始遍历(size-index)个 ,就可以得到
    //5、如果找到了返回该节点,否则返回null
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        //判断如果链表为空,返回null
        if (head.next == null) {
            return  null;//没有找到
        }
        //第一个遍历得到链表的长度(节点个数)
        int size = getLength(head);
        //第二次遍历size-index 位置,就是我们倒数的第K个节点
        //先做一个index的校验
        if (index <= 0 || index > size ){
            return null;
        }
        //定义给辅助变量
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) { //定位到倒数的index
            cur = cur.next;
        }
        return cur;
    }

3、单链表的反转(腾讯面试题)

 

//单链表的反转(腾讯面试题)
    //思路:
    //1、先定义一个节点reverseHead=new HeroNode();
    //2、从头到位遍历一遍,每遍历一个节点,就将其取出,并放在新的链表reverseNode的最前端
    //3、原来链表的head.next = reverseNode.next
    public static void reverseList(HeroNode head) {
        //如果当前链表为空,或只有一个节点,无需反转,直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义一个辅助变量,帮助遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null; // 指向当前节点【cur】的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        while (cur != null){
            next = cur.next; //暂时保存当前节点的下一个节点
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur; //将cur连接到新的链表上
            cur = next;//让cur指向下一个节点
        }
        //将head.next指向 reverseHead.next,实现单链表的反转
        head.next = reverseHead.next;
    }

4、从尾到头打印单链表

//从尾到头打印单链表
    //思路:
    //方式1、先将单链表进行一个反转操作,然后在遍历,问题:这样做的问题是会破坏原来的单链表的结构
    //方式2、利用这个栈的数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点
    /**
     * 方式二
     */
    public static  void  reveresPrint(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; //cur后移,这样压入后面一个节点
        }
        //将栈中的节点进行打印
        while (stack.size() > 0){
            System.out.println(stack.pop());//逆序的弹出
        }
    }

 

这篇关于Java数据结构和算法(单链表的面试题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!