03单链表面试题

声明：基于之前的代码这里只编写核心业务

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

这里判断的是有头结点的链表。

    /**
     * 获取链表有效结点个数  (这里的链表是有头结点的)
     * @param head  传入头结点就相当于传入的单链表
     * @return  有效结点个数
     */
    public static int getLength(HeroNode head){
        if (head.next == null){
            return 0;
        }
        HeroNode cur = head; // 拷贝head，head不能动
        int length = 0;
        while (true){
            if (cur.next == null){
                break;
            }
            cur = cur.next;
            length++;
        }
        return length;
    }

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

    /**
     * 查找单链表中倒数第n个结点
     *
     * @param head 头结点
     * @param n    倒数第一个元素
     * @return 返回结点
     * <p>
     * 思路
     * 1. 遍历一遍获得链表的总长度getLength
     * 2. 得到长度后遍历（length-n+1）个结点得到的就是
     * 3. 如果没有找到返回null
     */
    public static HeroNode getLastIndexNode(HeroNode head, int n) {
        //链表为空返回null
        if (head.next == null) {
            return null;
        }
        int length = getLength(head);//在这个方法中已经完成了一次遍历
        //判断这个n是否存在
        if (n < 0 || n > length) {
            return null;//根本找不到
        }
        HeroNode cur = head.next;
        for (int i = 0; i < (length - n); ++i) {
            cur = cur.next;
        }
        return cur;
    }

单链表的反转

import java.util.Stack;//使用栈需要引入包
/**
     * 反转链表
     * @param head 传入头结点;
     * 思路
     *  1. 创建一个新的链表
     *  2. 每遍历一个原链表结点将遍历的结点的next保存
     *  3. 将被遍历结点插入到新链表的head.next结点上
     */
    public static void reverseList(HeroNode head){
        //不需要反转的情况： 没有结点或者只有一个结点
        if (head.next == null || head.next.next == null){
            return;
        }
        HeroNode reverseHead = new HeroNode(0,"","");
        //定义辅助指针即备份变量
        HeroNode cur = head.next;
        HeroNode next = null;//存放思路中的2
        //这里的顺序特别的重要    
        // 在纸上画出草图 注意需要存储的结点及表达
        while (cur != null){
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

从尾到头打印单链表

/**
 * 从尾到头打印单链表
 * 方式1：反向遍历   即先反转 后打印
 *      但是这样破坏了原来的链表结构。
 * 方式2：使用栈 Stack
 *      将每个结点压入栈中然后弹栈  利用了栈的先进后出的思想
 */
public static void reversePrintByStack(HeroNode head){
    //如果为空 打印这是空链表
    if (head.next == null){
        System.out.println("这个链表是空的");
        return;
    }
    //creat a stack, push each node onto that.
    Stack<HeroNode> heroNodes = new Stack<>();
    HeroNode cur = head.next;
    while (cur != null){
        heroNodes.push(cur);
        cur = cur.next;
    }
    while (heroNodes.size()>0){
        System.out.println(heroNodes.pop());
    }
}

合并两个单链表，合并后的单链表仍然有序

    public static HeroNode margeLinkedList(HeroNode node1, HeroNode node2){
        //这里接受的是有头结点的链表，所以直接访问.next
        HeroNode cur1 = node1.next;
        HeroNode cur2 = node2.next;
        HeroNode head = new HeroNode(0,"","");
        HeroNode prev = head;
        while (cur1 != null && cur2!= null){
            if (cur1.no <= cur2.no){
                prev.next = cur1;
                cur1 = cur1.next;
            }else {
                prev.next = cur2;
                cur2 = cur2.next;
            }
            prev = prev.next;
        }
        prev.next = cur1 == null ? cur2 : cur1;//后面没有进行计算的链表可以直接连接到后面
        return head.next;
    }

测试用例及综合代码

package com.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //创建好多个结点
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "玉麒麟", "卢俊义");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode heroNode5 = new HeroNode(5, "鲁智深", "花和尚");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //singleLinkedList.addNode(heroNode1);
        //singleLinkedList.addNode(heroNode2);
        //singleLinkedList.addNode(heroNode3);

        singleLinkedList.addNodeByOrder(heroNode4);
        singleLinkedList.addNodeByOrder(heroNode2);
        singleLinkedList.addNodeByOrder(heroNode3);
        singleLinkedList.addNodeByOrder(heroNode1);
        singleLinkedList.addNodeByOrder(heroNode3);
        singleLinkedList.addNodeByOrder(heroNode5);
        singleLinkedList.showList();

        System.out.println("==========修改后的信息==========");
        singleLinkedList.updateNode(new HeroNode(5, "花荣", "小李广"));
        singleLinkedList.updateNode(new HeroNode(8, "花荣", "小李广"));
        singleLinkedList.showList();

        System.out.println("========删除后的结点信息=========");
        singleLinkedList.deleteNode(1);
        singleLinkedList.deleteNode(8);
        singleLinkedList.showList();

        System.out.println("========获取链表有效结点个数=========");
        System.out.println(getLength(singleLinkedList.getHead()));

        System.out.println("========得到倒数第n个结点========");
        System.out.println(getLastIndexNode(singleLinkedList.getHead(),2));

        //System.out.println("=========反转链表==========");
        //reverseList(singleLinkedList.getHead());
        //singleLinkedList.showList();

        System.out.println("==========从尾到头打印链表===========");
        reversePrintByStack(singleLinkedList.getHead());

        System.out.println("==========合并两个链表==========");
        //创建好多个结点
        HeroNode node1 = new HeroNode(1, "1", "1");
        HeroNode node2 = new HeroNode(2, "2", "2");
        HeroNode node3 = new HeroNode(3, "3", "3");
        HeroNode node4 = new HeroNode(4, "4", "4");
        HeroNode node5 = new HeroNode(5, "5", "5");
        HeroNode node6 = new HeroNode(6, "6", "6");
        SingleLinkedList list1 = new SingleLinkedList();
        SingleLinkedList list2 = new SingleLinkedList();
        list1.addNode(node1);
        list1.addNode(node3);
        list1.addNode(node5);
        list2.addNode(node2);
        list2.addNode(node4);
        list2.addNode(node6);
        SingleLinkedList list3 = new SingleLinkedList();
        list3.addNode(margeLinkedList(list1.getHead(),list2.getHead()));
        list3.showList();
    }

    /**
     * 获取链表有效结点个数  (这里的链表是有头结点的)
     *
     * @param head 传入头结点就相当于传入的单链表
     * @return 有效结点个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        HeroNode cur = head; // 拷贝head，head不能动
        int length = 0;
        while (true) {
            if (cur.next == null) {
                break;
            }
            cur = cur.next;
            length++;
        }
        return length;
    }

    /**
     * 查找单链表中倒数第n个结点
     *
     * @param head 头结点
     * @param n    倒数第一个元素
     * @return 返回结点
     * <p>
     * 思路
     * 1. 遍历一遍获得链表的总长度getLength
     * 2. 得到长度后遍历（length-n+1）个结点得到的就是
     * 3. 如果没有找到返回null
     */
    public static HeroNode getLastIndexNode(HeroNode head, int n) {
        //链表为空返回null
        if (head.next == null) {
            return null;
        }
        int length = getLength(head);//在这个方法中已经完成了一次遍历
        //判断这个n是否存在
        if (n < 0 || n > length) {
            return null;//根本找不到
        }
        HeroNode cur = head.next;
        for (int i = 0; i < (length - n); ++i) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 反转链表
     * @param head 传入头结点;
     * 思路
     *  1. 创建一个新的链表
     *  2. 每遍历一个原链表结点将遍历的结点的next保存
     *  3. 将被遍历结点插入到新链表的head.next结点上
     */
    public static void reverseList(HeroNode head){
        //不需要反转的情况： 没有结点或者只有一个结点
        if (head.next == null || head.next.next == null){
            return;
        }
        HeroNode reverseHead = new HeroNode(0,"","");
        //定义辅助指针即备份变量
        HeroNode cur = head.next;
        HeroNode next = null;//存放思路中的2
        //这里的顺序特别的重要
        // 在纸上画出草图 注意需要存储的结点及表达
        while (cur != null){
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

    /**
     * 从尾到头打印单链表
     * 方式1：反向遍历   即先反转 后打印
     *      但是这样破坏了原来的链表结构。
     * 方式2：使用栈 Stack
     *      将每个结点压入栈中然后弹栈  利用了栈的先进后出的思想
     */
    public static void reversePrintByStack(HeroNode head){
        //如果为空 打印这是空链表
        if (head.next == null){
            System.out.println("这个链表是空的");
            return;
        }
        //creat a stack, push each node onto that.
        Stack<HeroNode> heroNodes = new Stack<>();
        HeroNode cur = head.next;
        while (cur != null){
            heroNodes.push(cur);
            cur = cur.next;
        }
        while (heroNodes.size()>0){
            System.out.println(heroNodes.pop());
        }
    }

    /**
     * 合并连个链表，合并完仍然有序
     * @param node1 链表1的头结点
     * @param node2 链表2的头结点
     * @return  合并后链表的头结点
     */
    public static HeroNode margeLinkedList(HeroNode node1, HeroNode node2){
        //这里接受的是有头结点的链表，所以直接访问.next
        HeroNode cur1 = node1.next;
        HeroNode cur2 = node2.next;
        HeroNode head = new HeroNode(0,"","");
        HeroNode prev = head;
        while (cur1 != null && cur2!= null){
            if (cur1.no <= cur2.no){
                prev.next = cur1;
                cur1 = cur1.next;
            }else {
                prev.next = cur2;
                cur2 = cur2.next;
            }
            prev = prev.next;
        }
        prev.next = cur1 == null ? cur2 : cur1;//后面没有进行计算的链表可以直接连接到后面
        return head.next;
    }
}


//使用单链表来管理英雄
class SingleLinkedList {
    //初始化一个头结点，一般不能动,
    // 而且每创建一个单链表都需要创建一个头。
    // 所以不需要将他修饰为static final
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    //添加结点
    public void addNode(HeroNode hero) {
        //找到最后一个结点
        //因为head结点不能用，所以先拷贝一份
        HeroNode temp = head;
        while (true) {
            //最后一个结点特点，结点的next属性值为null
            if (temp.next == null) {
                break;
            }
            temp = temp.next;//指针后移
        }
        //完成上面的循环以后temp指向的是最后一个结点
        temp.next = hero;
    }

    //根据序号来添加。
    public void addNodeByOrder(HeroNode hero) {
        //同理，做一个拷贝
        HeroNode temp = head;
        boolean flag = false; //添加的编号是否存在
        //这个指针要找到添加位置的前一个结点。
        while (true) {
            if (temp.next == null) {
                break;//如果此时就是最后一个结点
            }
            //下面这两个顺序不能交换，一定是先判断是否存在再判断下一个编号是否大
            if (temp.no == hero.no) {
                flag = true;//此时已经存在了
                break;
            }
            if (temp.next.no > hero.no) {
                break;//位置找到了在这个后面添加
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("准备加入的英雄%d  %s已经存在了，不能添加\n", hero.no, hero.name);
        } else {
            //插入到temp后面 -- 这个顺序不能搞错了。
            hero.next = temp.next;
            temp.next = hero;
        }
    }

    //修改结点信息，通过newHero.no进行定位。同时注意no不能改变。
    public void updateNode(HeroNode newHero) {
        /**
         * 思路
         * 1. 判断是否为空
         * 2. 找到需要修改的结点
         */
        if (head.next == null) {
            System.out.println("链表为空，不满足修改条件");
            return;
        }

        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp == null) {      //遍历完了都没有找到
                break;//已经遍历结束了
            }
            if (temp.no == newHero.no) {
                flag = true;
                break;

            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newHero.name;
            temp.nickName = newHero.nickName;
        } else {
            System.out.printf("没有找到 编号为 %d 的结点信息，不能修改\n", newHero.no);
        }
    }

    //删除结点 -- 通过英雄编号，即hero.no

    /**
     * 思路：
     * 1. 我们先找到需要删除的这个结点的前一个结点
     * 2. temp.next = temp.next.next
     * 3. 被删除的结点，将不会有其它引用指向，剩下的交给java的垃圾回收机制。
     */
    public void deleteNode(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            //已经到链表的最后了，还没有找到
            if (temp.next == null) {
                break;
            }

            //找到的情况
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //业务处理
        if (flag) {
            temp.next = temp.next.next;
            System.out.printf("成功删除编号为 %d 的结点\n", no);
        } else {
            System.out.printf("没有找到编号为 %d 的结点\n", no);
        }
    }

    //显示链表【遍历】
    public void showList() {
        /**
         * 1. 判断链表是否为空。
         * 2. 因为头结点不能动，所以拷贝一份。temp
         */
        if (head.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        //因为头结点没有使用，所以第一个显示的结点就是head.next
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;//变量后移
        }
    }
}

//定义HeroNode（存放英雄数据的结点）
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    //构造器
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}