数据结构与算法学习四：单链表面试题，新浪、腾讯【有难度】、百度面试题

前言

• 总结一下单链表的面试题，对其详细的描述。
• 这个的方法 我都放在了 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个节点。
6. 如果找到了，则返回该节点，否则返回nulll

2.3 代码实现

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

三、 腾讯面试题【有难度】

3.1 问题描述

将单链表反转。

3.2 思路分析

思路：

1. 先定义一个节点 HeroNode reverseHead = new HeroNode(0, "", "");
2. 在定义一个 辅助节点和 next节点（用于存放当前节点的下一个节点，因为后面需要使用）。
   HeroNode temp = head.next;
   HeroNode next = null;
3. 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端。temp.next = reverseHead.next ，这句话就是将反转链表的后面赋给拿下来的 temp 当前节点。
4. 将当前拿下来的节点，放到 reverseHead 上。
5. 最后，将 temp 节点后移：temp = next;

3.3 代码实现

/*
 * 将单链表反转 【腾讯面试题】
 * */
public static void reverseList(HeroNode head) {
    //如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }

    //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    HeroNode temp = head.next;
    HeroNode next = null;
    HeroNode reverseHead = new HeroNode(0, "", "");

    /*
     * 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
     * 动脑筋
     * */
    while (temp != null) {
        next = temp.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
        temp.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
        reverseHead.next = temp;//将cur 连接到新的链表上
        temp = next;//让cur后移
    }
    //将head.next 指向 reverseHead.next , 实现单链表的反转
    head.next = reverseHead.next;
}

四、 百度面试题

4.1 问题描述

从尾到头打印单链表

4.2 思路分析

• 第一种方式： 反向遍历。先将链表反转，在遍历打印（借用腾讯面试题）。但是这样会改变链表数据结构，而题目仅是逆序打印而已。
• 第二种方式：借用stack 栈 的先进后出的特点来完成逆序打印。

1. 思路分析：
   可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.

举例演示栈的使用 Stack

4.3 代码实现

/*
 * 方法：实现单链表的逆序打印【百度面试题】
 * 方式1：先反转，在打印。
 * 方式2：利用栈 这个数据结构，将各个节点压入栈中，然后利用栈的先进先出的特点，实现逆序打印的效果
 * */
 public static void reversePrint(HeroNode head){
     if (head.next == null){
         return;
     }

     Stack<HeroNode> stack = new Stack<>();
     HeroNode temp = head.next;
     while (temp != null){
         stack.push(temp);
         temp = temp.next;
     }
     while (stack.size()>0){
         System.out.println(stack.pop());
     }
 }

五、所有测试放一块

package com.feng.ch03_singlelinkedlist;

import java.util.Stack;

public class SingleLinkedListMain {
    public static void main(String[] args) {
        // 测试
        // 先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 添加节点
//        singleLinkedList.addLinked(hero1);
//        singleLinkedList.addLinked(hero2);
//        singleLinkedList.addLinked(hero4);
//        singleLinkedList.addLinked(hero3);

        singleLinkedList.addLinkedByOrder(hero1);
        singleLinkedList.addLinkedByOrder(hero2);
        singleLinkedList.addLinkedByOrder(hero4);
        singleLinkedList.addLinkedByOrder(hero3);
        // 显示节点
        System.out.println("显示初始添加后的节点~");
        singleLinkedList.list();

        // 测试修改
        System.out.println();
        System.out.println("测试修改后的结果");
        HeroNode updateNode = new HeroNode(2, "小卢", "玉麒麟");
        singleLinkedList.updateNode(updateNode);
        singleLinkedList.list();

        // 测试删除
        System.out.println();
        System.out.println("测试删除后的结果");
        singleLinkedList.deleteNode(2);
        singleLinkedList.deleteNode(3);
        singleLinkedList.list();

        // 测试返回单链表有效个数
        System.out.println();
        System.out.println("单链表有效个数=" + getLength(singleLinkedList.getHead()));

        // 测试 查看倒数第 K 个节点的 数据
        System.out.println();
        HeroNode lastIndexNode = findLastIndexNode(singleLinkedList.getHead(), 1);
        System.out.println("倒数第 K 个节点的res=" + lastIndexNode);

        // 测试单链表的反转
        System.out.println();
        System.out.println("测试反转后的链表");
        reverseList(singleLinkedList.getHead());
        singleLinkedList.list();

        // 测试单链表的逆序打印
        System.out.println();
        System.out.println("测试单链表的逆序打印");
        reversePrint(singleLinkedList.getHead());
    }
}