跳到主要内容

四：单链表面试题，新浪、腾讯【有难度】、百度面试题

前言​

  • 总结一下单链表的面试题，对其详细的描述。
  • 这个的方法 我都放在了 SingleLinkedListMain 类中，写成了静态方法。

一、 求单链表中有效的个数​

1.1 问题描述​

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

1.2 思路分析​

直接遍历即可，设置一个增加器。

1.3 代码实现​

/*
     * 方法：获取单链表的有效节点个数（如果是带头结点的链表，需要不统计头结点）
     * @param head 链表的头节点
     * @return 返回的就是有效节点的个数
     * */
    public static int getLength(HeroNode head) {
   
     
        if (head.next == null) {
   
     
            return 0;
        }
        HeroNode temp = head.next;
        int count = 0;
        /*while (true){
            if (temp== null){
                break;
            }
            count++;
            temp = temp.next;
        }*/
        while (temp != null) {
   
     
            count++;
            temp = temp.next;
        }
        return count;
    }

二、 新浪面试题​

2.1 问题描述​

查找单链表中的倒数第k个结点

2.2 思路分析​

思路：

1、 编写一个方法，接收head节点，同时接收一个index；
2、 index表示是倒数第index个节点；
3、 先把链表从头到尾遍历，得到链表的总的长度size=getLength(),这个方法为上面例题；
4、 对index进行数据校验，小于0，大于size，都返回null；
5、 得到size后，我们从链表的第一个开始遍历(size-index)个，就得到了倒数第K个节点；