单向链表CURD+常见面试题

import java.util.Stack;

/**
 * 单向链表CURD
 */
public class SingleLinkedListDemo {

    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.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);
//         显示数据
        singleLinkedList.list();
        System.out.println("-------------------------------");
        HeroNode herou = new HeroNode(2, "俊义", "玉麒麟");
        singleLinkedList.update(herou);
        singleLinkedList.list();
        System.out.println("-------------------------------");
        singleLinkedList.delete(4);
//        singleLinkedList.delete(3);
//        singleLinkedList.delete(2);
//        singleLinkedList.delete(1);
        singleLinkedList.list();
    }
}

/**
 * 单向链表
 * 说明：链表的各个节点不一定是连续的(链式存储)
 */
class SingleLinkedList {
    // 先初始化头节点，头节点不要动，不存放具体的数据
    public HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加节点到单向链表(直接加到尾部)
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        // head不能动，需要一个辅助遍历temp
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        // 循环结束，temp到达尾部，将下一个节点设为传入的参数
        temp.next = heroNode;
    }

    /**
     * 按照编号顺序插入
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        // head不能动，需要一个辅助遍历temp
        HeroNode temp = head;
        boolean flag = false; // 标识添加的编号是否存在，默认为false
        while (true) {
            if (temp.next == null) { // 边界条件独立处理
                break;
            }
            if (temp.next.no > heroNode.no) { // temp后面插入
                break;
            } else if (temp.next.no == heroNode.no) { // 已经存在，无法加入
                flag = true;
                break;
            }
            temp = temp.next; // 移动指针
        }
        if (flag) { // 无法插入
            System.out.println("无法插入~");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    /**
     * 修改节点数据
     *
     * @param heroNode
     */
    public void update(HeroNode heroNode) {
        if (head.next == null) { // 空链表
            System.out.println("链表为空~");
            return;
        }

        // 定义辅助变量，存储头节点
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) { //遍历结束
                break;
            }
            if (temp.no == heroNode.no) { // 找到对应位置
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else
            System.out.println("未找到需修改的数据~");
    }

    /**
     * 删除节点
     *
     * @param no
     */
    public void delete(int no) {
        HeroNode temp = head;
        boolean flag = false; // 标志是否找到待删除节点
        while (true) {
            if (temp.next == null)
                break;
            if (temp.next.no == no) { // 找到待删除节点的前一个节点temp
                flag = true;
                break;
            }

            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next; // 跨越待删除的数据，待删除的数据会被JVM回收
        } else
            System.out.println("待删除的节点不存在~");

    }

    /**
     * 显示链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }

        // 记录头节点
        HeroNode temp = head.next; // 头结点指示，实际数据从head.next开始
        while (temp != null) { // 到达尾部
            System.out.println(temp); // 输出数据
            temp = temp.next; // 指针后移
        }

    }

    /**
     * 链表长度
     *
     * @param heroNode
     * @return
     */
    public static int getLength(HeroNode heroNode) {
        if (heroNode.next == null) { // 静态方法中调用静态变量
            return 0;
        }
        int length = 0;
        HeroNode temp = heroNode;
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    /**
     * 获取链表倒数第k个节点
     *
     * @param k
     * @return
     */
    public static HeroNode queryLastIndexNode(HeroNode heroNode, int k) {
        if (heroNode.next == null) {
            return null;
        }

        int size = getLength(heroNode); // size - k
        // 校验k
        if (k <= 0 || k > size) {
            return null;
        }

        HeroNode temp = heroNode;
        for (int i = 0; i < (size - k); i++) {
            temp = temp.next;
        }

        return temp.next;
    }

    /**
     * 反转链表
     *
     * @param heroNode
     * @return
     */
    public HeroNode reverseLinkedList(HeroNode heroNode) {
        if (heroNode.next == null || heroNode.next.next == null) {
            return heroNode; // 链表不变
        }

        // 定义一个辅助的指针，帮助遍历链表
        HeroNode temp = heroNode.next;
        HeroNode next = null; // 指向当前节点(temp)的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");

        // 遍历原来的链表，每遍历一个链表，就将其取出，并放在新的链表reverseHead的最前端
        while (temp != null) {
            next = temp.next; // 存储当前节点的下一节点
            temp.next = reverseHead.next; // 将temp的下一个节点指向新链表reverseHead的最前端
            reverseHead.next = temp; // 将temp连接到新的链表上
            temp = next; // 最后移动指针
        }

        heroNode.next = reverseHead.next;
        return heroNode;
    }

    /**
     * 倒序打印单链表
     * 方法1：反转链表再遍历(破坏原链表结构)
     * 方法2：栈实现
     *
     * @param heroNode
     */
    public void reversePrintLinkedList(HeroNode heroNode) {
        if (heroNode.next == null) {
            return;
        }

        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode temp = heroNode.next;
        while (temp != null) {
            stack.push(temp); // 入栈
            temp = temp.next;
        }

        while (stack.size() > 0) {
            System.out.println(stack.pop()); // 出栈
        }
    }

    /**
     * 合并两个有序链表(升序)
     *
     * @param heroNode1
     * @param heroNode2
     * @return
     */
    public HeroNode mergeLinkedList(HeroNode heroNode1, HeroNode heroNode2) {
        if (heroNode1 == null) {
            return heroNode2;
        }
        if (heroNode2 == null) {
            return heroNode1;
        }
        SingleLinkedList singleLinkedList = new SingleLinkedList(); // 用于操作链表
        while (heroNode1 != null && heroNode2 != null) {
            if (heroNode1.no > heroNode2.no) {
                singleLinkedList.add(heroNode2); // 添加到全局变量head中
                heroNode2 = heroNode2.next;
            } else {
                singleLinkedList.add(heroNode1); // 添加到全局变量head中
                heroNode1 = heroNode1.next;
            }
        }
        while (heroNode1 == null) {
            singleLinkedList.add(heroNode2);
            heroNode2 = heroNode2.next;
        }
        while (heroNode2 == null) {
            singleLinkedList.add(heroNode1);
            heroNode1 = heroNode1.next;
        }
        return head;
    }
}

/**
 * 定义HeroNode，每个HeroNode对象就是一个节点
 */
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一个节点(为null时为链表尾部)

    /**
     * 构造方法
     *
     * @param no       编号
     * @param name     姓名
     * @param nickname 昵称
     */
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    /**
     * 重写toString()方法为了显示
     *
     * @return
     */
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}