day02-单链表

链表

1. 链表是以节点的方式进行存储的。

2. 每个节点包含：data域 和 next域：指向下一个节点。

3. 链表的各个节点不一定是连续存储的。

4. 链表分为带头结点的和不带头节点的。

Node 节点

public class HeroNode {
    private int no; // 编号
    private String name; //名字
    private String nickname; // 外号
    private 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 + '\'' +
                '}';
    }

    public void setNo(int no) {
        this.no = no;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setNickname(String nickname) {
        this.nickname = nickname;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

    public int getNo() {
        return no;
    }

    public String getName() {
        return name;
    }

    public String getNickname() {
        return nickname;
    }

    public HeroNode getNext() {
        return next;
    }
}

SingleLinkedList 单链表

public class SingleLinkedList {

    //创建头节点
    public HeroNode head = new HeroNode(0,"","");

    // 打印节点
    public void showLinked(){
        // 判断链表是否为空
        if (head.getNext()==null){
            System.out.println("链表为空");
            return;
        }
        // 链表不为空循环遍历打印输出
        HeroNode temp = head.getNext();
        while (true){
            //判断是否为尾节点
            if (temp==null) {
                break;
            }
            //不是则打印下一个节点
            System.out.println(temp);
            //指针后移
            temp = temp.getNext();
        }
    }


    // 添加节点
    public void addNode(HeroNode heroNode){
        //先找到尾部节点再进行插入
        //创建一个temp指针进行遍历,这里我就直接让temp指向头结点的下一个节点
        HeroNode temp = head;
        while (true){
            //判断节点是否为空
            if (temp.getNext()==null){
                break;
            }
            //不是尾节点指针后移
            temp = temp.getNext();
        }
        //经过遍历temp就是尾部节点
        temp.setNext(heroNode);
    }

    /**
     * 按照编号添加节点
     */
    public void addByOrder(HeroNode heroNode){
        //由于是单链表temp只能在插入节点之前！！！
        HeroNode temp = head;
        boolean flag = false;//判断插入的编号是否存在
        while (true){
            // 查看是不是最后一个节点
            if (temp.getNext()==null){break;}
            // 查看插入的位置
            if (temp.getNext().getNo()>heroNode.getNo()){
                //位置找到就应该在temp的后面添加
                break;
            }else if(temp.getNext().getNo() == heroNode.getNo()){
                //说明编号已经存在
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (flag){
            //不能插入文字提示
            System.out.printf("待插入的英雄（编号：%d）已经存在\n",heroNode.getNo());
        }else {//插入内容
            heroNode.setNext(temp.getNext());
            temp.setNext(heroNode);
        }
    }

    /**
     * 根据no来修改节点信息,即no 不能发生改变
     */
    public void update(HeroNode heroNode){

        //判断练表是否为空
        if (head.getNext()==null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.getNext();
        boolean flag = false; //判断链表是否找到这个节点
        while (true){
            //判断链表是否为空
            if (temp == null){
                break;
            }
            // 判断链表是否找到这个节点
            if (temp.getNo()==heroNode.getNo()){
                flag=true;
                break;
            }
            temp = temp.getNext();
        }
        //判断链表是否找到这个节点
        if (flag){
           temp.setName(heroNode.getName());
           temp.setNickname(heroNode.getNickname());
        }else {
            System.out.println("链表不存在此节点:"+heroNode);
        }
    }

    /**
     * 根据no删除节点
     * temp.next = temp.next.next
     * 未被引用的节点会被JVM的垃圾回收机制回收
     */
    public void delete(int no){
        HeroNode temp = head;
       //是否找到删除节点
        boolean flag = false;
        while (true){
            //判断链表是否为空
            if (temp.getNext()==null){
                break;
            }
            if (temp.getNext().getNo()==no){
                //找到节点
                flag = true;
                break;
            }
            temp = temp.getNext();//指针后移，继续遍历
        }
        if (flag){
            temp.setNext(temp.getNext().getNext());
        }else {
            System.out.println("删除====该节点值不存在");
        }
    }
}

链表的面试题

1. 求单链表中有效节点的个数。
2. 查找单链表中的倒数第K个结点。==新浪面试题==
3. 链表的反转。==腾讯面试题==
4. 从尾到头打印单链表。==百度== 方式1：反向遍历2：Stack栈
5. 合并两个有序的单链表，合并之后的链表仍然有序。（课后练习）

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

    //题目1：方法：取到单链表的节点个数（不计入头节点）
    /**
     * @param head 链表的头节点
     * @return 返回有效节点个数
     */
    public static int getLength(HeroNode head){
        if (head.getNext()==null){//空链表
            return 0;
        }
        int length = 0;
        HeroNode temp = head.getNext();
        while (temp!=null){
            length++;
            temp = temp.getNext();
        }
        return length;
    }

2. 查找单链表中的倒数第K个结点。==新浪面试题==

//题目2：查找单链表中的倒数第K个结点
    //思路：将倒数变成正数
    public HeroNode findLastIndexNode(HeroNode head,int index){
        if (head.getNext()==null){//空链表
            return null;
        }
        //第一次遍历获取链表长度
        int length = getLength(head);
        //第二次遍历寻找值
        //判断index是否合法
        if (index < 0 || index >length){
            return null;
        }
        HeroNode cur = head.getNext();
        // 遍历寻找
        for (int i = 0; i < length - index; i++) {
            cur = cur.getNext();
        }
        return cur;
    }

3. 链表的反转。==腾讯面试题==

 public void reverseList(HeroNode head){
        //判断如果链表为空或者链表只有一个节点则不需要操作
        if (head.getNext()==null || head.getNext().getNext()==null){
            return;
        }
        //定义辅助遍历来帮助我们遍历链表
        HeroNode cur = head.getNext();
        HeroNode next = null;// 指向cur下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表，没遍历一个节点就将其放到reverseHead的最前端
        while (cur!=null){
            next = cur.getNext(); //next 来保存遍历的位置
            cur.setNext(reverseHead.getNext());
            reverseHead.setNext(cur);
            cur = next;
        }
        head.setNext(reverseHead.getNext());
    }

4. 题目4：从尾到头打印单链表

  //题目4：从尾到头打印单链表
    // 方法：
    // 1. 反转链表  会改变原有数据的结构，并且操作复杂度高，不推荐
    // 2. stack栈的方式  适用栈的特点：先进后出  将数据压入栈中 再取出数据就会反过来
    public void reversePrint(HeroNode head){
        if (head.getNext()==null){//判断链表是否为空
            return;
        }
        HeroNode cur = head.getNext();//设置辅助指针
        Stack<HeroNode> stack = new Stack<>();// 使用栈
        while (cur!=null){
            stack.push(cur);
            cur = cur.getNext();
        }
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }