Day04单链表面试题

实现代码

public static int getValidNode(HeroNode head){
    int num = 0;
    // 链表为空
    if (head.next == null){
        return num;
    }
    // 排除头结点
    HeroNode temp = head.next;
    while (temp != null){
        // 有效节点数+1
        num++;
        // 后移
        temp = temp.next;
    }
    return num;
}

测试代码

public static void main(String[] args) {
    HeroNode node1 = new HeroNode(1, "李逵", "黑旋风");
    HeroNode node2 = new HeroNode(2, "宋江", "及时雨");
    HeroNode node3 = new HeroNode(3, "吴用", "智多星");
    HeroNode node4 = new HeroNode(4, "林冲", "豹子头");
    // 初始化链表
    SinglelinkedList linkedList = new SinglelinkedList();
    // 添加英雄
    linkedList.addByOrder(node1);
    linkedList.addByOrder(node4);
    linkedList.addByOrder(node4);
    linkedList.addByOrder(node3);
    linkedList.addByOrder(node3);
    linkedList.addByOrder(node2);
    // 打印
    linkedList.findAlllink();
    // 统计节点有效个数
    System.out.println("有效的英雄节点数为：" + getValidNode(linkedList.getHead()));
}

结果

实现代码

public static HeroNode findInverseNode(HeroNode head, int n) {
    if (head.next == null) {
        return null;
    }
    // 排除头结点
    HeroNode cur = head.next;
    int validNum = getValidNode(head);
    boolean flag = false;
    // 对于 请求参数的合法性校验
    if (n > validNum || n < 0) {
        return null;
    }
    // 转换成 正数 的
    n = validNum - n;
    // 计数用的哨兵
    int count = 0;
    // 当然这里也可以用for循环
    while (true) {
        if (cur == null) {
            break;
        }
        if (n == count) {
            // 找到目标
            flag = true;
            break;
        }
        count++;
        // 后移
        cur = cur.next;
    }
    if (flag) {
        return cur;
    }
    return null;
}

测试代码

// 查找单链表中的 倒数 第k个结点
int k = 4;
System.out.println("英雄信息为：" + findInverseNode(linkedList.getHead(), k));

效果图

实现代码

public static HeroNode reverselink(HeroNode head) {
    // 当只有一个节点，或者一个节点都没有时
    if (head.next == null || head.next.next == null) {
        System.out.println("无需反转");
        return head;
    }
    // 遍历正向链表的（原来的链表）
    HeroNode temp = head.next;
    // 存储临时的temp变量（注意事项是地址传递）
    HeroNode copy = null;
    // 存储反向链表的
    HeroNode reverseHead = new HeroNode(0, "", "");
    while (temp != null) {
        // 赋值 （注意这里是地址传递，并非值传递）
        copy = temp;
        // 后移
        temp = temp.next;
        // 头插法
        copy.next = reverseHead.next;
        reverseHead.next = copy;
    }
    return reverseHead;
}


public static void queryAll(HeroNode head) {
    HeroNode temp = head.next;
    int i = 1;
    if (head.next == null) {
        System.out.println("当前链表为空，无数据可以打印！");
        return;
    }
    while (temp != null) {
        System.out.println("第" + i + "个英雄信息如下:" + temp.toString());
        // 后移
        temp = temp.next;
        i++;
    }
}

测试代码

// 反向链表
System.out.println("反向链表");
HeroNode reverselink = reverselink(linkedList.getHead());
queryAll(reverselink);

效果图

方式1：反向遍历：其实就是反转链表（就是第三道面试题的方法），不建议使用，因为那样会破坏原有的链表结构！万一后续需要在打印正向链表呢，所以只改变打印顺序即可。

方式2：Stack栈

实现代码

public static Stack reservePrintlink(HeroNode head) {
    Stack stack = new Stack<>();
    HeroNode temp = head.next;
    if (head.next == null) {
        System.out.println("当前链表为空，无数据可以打印！");
        return null;
    }
    while (temp != null) {
        // 入栈
        stack.push(temp);
        // 后移
        temp = temp.next;
    }
    return stack;
}


public static void getAllStack(Stack stack){
    while(stack.size() > 0){
        System.out.println(stack.pop() + "出栈");
    }
}

测试代码

// 方向打印链表
System.out.println("测试反向链表打印");
Stack nodeStack = reservePrintlink(linkedList.getHead());
getAllStack(nodeStack);

运行结果