链表(Linked List)介绍

链表是有序的列表，但是它在内存中是存储如下

链表是以节点的方式来存储,是链式存储。

每个节点包含 data 域， next 域：指向下一个节点。

如图：发现链表的各个节点不一定是连续存储。

链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

单链表(带头结点) 逻辑结构示意图

1. 单链表的应用实例

1.1 概念解读（重要）

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作。

关于下面及代码中的temp（临时对象）解析

重要的概念：

head是我们定义的一个空虚的链表头

next是我们的下一个类（英雄），就是这些next一个接一个组成了我们的链表。

通俗的说，你有个朋友叫小明，小明有个朋友小红，小红有个朋友叫小蓝，于是 你-小明-小红-小蓝 一起组成了一条单链表。只不过你前面有一个看不见的辅助指针帮你们把这条朋友链给维护好。

由于后面的几个方法比较简单，我没有多加解释，实际上大家可以不用看图，直接上代码敲，有什么不懂的参考一下我的代码，加上你自己的思考，肯定能拿下这个的。

添加英雄(1)

第一种方法是直接添加到链表的尾部

思路分析示意图：

添加英雄(2)

第二种方法是根据排名**将英雄插入到指定位置(如果已经存在这个排名，则添加失败，并给出提示)

思路的分析示意图：

修改节点

思路：

1. 先找到该节点，通过遍历
2. temp.name = newHeroNode.name
3. temp.nickname= newHeroNode.nickname

删除节点

思路分析的示意图：

显示链表

思路：

1. 通过head.next判断链表是否有值，有的话继续
2. 让temp=head.next
3. 当temp不为空时，循环为true，打印temp后让temp=temp.next

1.2 代码实现

package com.xn2001.linkedlist;

/**
 * @author 乐心湖
 * @date 2020/8/13 23:52
 **/
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.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
        //第二种添加方法的测试
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        //显示
        singleLinkedList.list();
        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();
        //删除一个节点
        singleLinkedList.del(1);
        singleLinkedList.del(4);
        System.out.println("删除后的链表情况~~");
        singleLinkedList.list();
    }
}

class SingleLinkedList {

    //先初始化一个头节点, 头节点不要动, 不存放任何具体数据
    private final HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加节点到单向链表
     * 思路，当不考虑编号顺序时
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的 next 指向新的节点
     */
    public void add(HeroNode heroNode) {
        //因为 head 节点不能动，永远在第一位，因此我们需要一个辅助遍历 temp
        HeroNode temp = head;
        //遍历链表，找到最后一个
        while (temp.next != null) {
            temp = temp.next;
        }
        //当退出 while 循环时，temp 就指向了链表的最后
        //将最后这个节点的 next 指向 新的节点
        temp.next = heroNode;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false; // flag标志添加的编号是否存在
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == heroNode.no) {
                flag = true; //说明编号存在
                break;
            }
            if (temp.next.no > heroNode.no) {
                break;
            }
            temp = temp.next; //后移，遍历当前链表
        }
        if (flag) {
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
        } else {
            //插入到链表中, temp的后面
            //先把原来后面的数给heroNode.next
            heroNode.next = temp.next;
            //然后换掉temp.net
            temp.next = heroNode;
        }
    }

    //显示链表[遍历] 、
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改.
    //根据 newHeroNode 的 no 来修改即可
    public void update(HeroNode newHeroNode) {
        //判断是否空
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        //找到需要修改的节点, 根据 no 编号
        //定义一个辅助变量
        HeroNode temp = head;
        //表示是否找到该节点
        boolean flag = false;
        while (true) {
            //已经遍历完链表
            //注意这里面向的是temp，前面的添加英雄面向的是temp的下一个
            if (temp == null) {
                break;
            }
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据 flag 判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            //没有找到
            System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
        }
    }

    //删除节点
    //1. head 不能动，因此我们需要一个 temp 辅助节点找到待删除节点的前一个节点
    //2. 说明我们在比较时，是 temp.next.no 和 需要删除的节点的 no 比较
    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false; // 标志是否找到待删除节点的
        while (temp.next != null) {
            //已经遍历完链表
            //注意这里面向的是temp.next，我们要把next改成next.next，就可以把next去掉了
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //判断 flag
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }
    }
}

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 + "]";
    }
}

1.3 单链表面试题

常见的面试题

求单链表中有效节点个数

方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)

/**
 * @param head 单链表的头节点
 * @return 返回有效节点的个数
 */
public static int getLength(HeroNode head) {
    int length = 0;
    HeroNode temp = head.next;
    while (temp != null) {
        length++;
        temp = temp.next;
    }
    return length;
}

查找单链表中的倒数第k个节点

思路：

1. 编写一个方法，接收 head 节点，同时接收一个 index
2. index 表示是传进来的倒数第 index 个节点
3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
4. 得到 length后，我们从链表的第一个开始遍历 (length-index)个，就可以得到
5. 如果找到了，则返回该节点，否则返回 nulll

public static HeroNode findLastIndexNode(HeroNode head, int index) {
    int length = getLength(head);
    if (index > length || length <= 0) {
        return null;
    }
    HeroNode temp = head.next;
    for (int i = 0; i < length-index; i++) {
        temp = temp.next;
    }
    return temp;
}

单链表的反转

反转最核心的就是把第一个node（示例中的英雄）加到新的node的next中，然后新的node放到第一位。

方式一：就地反转法就是在遍历的时候有遇到新的数就拿来放到第一个。

方式二：头插法只不过用了一个新的辅助链表头，在这条链表下一直往最前面插入值，最后把原链表头的enxt指向辅助链表头的next就可以了。

就地反转法

把当前链表的下一个节点pCur插入到头结点dummy的下一个节点中，就地反转。

图解

pCur是需要反转的节点

1. prev连接下一次需要反转的节点
2. 反转节点pCur
3. 纠正头结点dummy的指向
4. pCur指向下一次要反转的节点

好好体会图解，收获很大的。

学习参考于 https://www.cnblogs.com/byrhuangqiang/p/4311336.html

public static void reversetListOne(HeroNode head) {
    // 声明当前节点，前继节点和后继节点
    HeroNode prev = head.next;
    HeroNode pCur = prev.next;
    while (pCur != null) {
        //将prev后移
        prev.next = pCur.next;
        //这里是把原来的链表一号拼接在pCur后面
        pCur.next = head.next;
        //将pCur移到最前成为一个新的链表一号
        head.next = pCur;
        //让pCur回归到修改后prev的后面，方便下一个循环
        pCur = prev.next;
    }
}

头节点插入法

新建一个头结点，遍历原链表，把每个节点用头结点插入到新建链表中。最后，新建的链表就是反转后的链表。

public static void reverseListTwo(HeroNode head) {
    //如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }
    //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    HeroNode cur = head.next;
    HeroNode next;
    HeroNode reverseHead = new HeroNode(0, "", "");
    //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
    while (cur != null) {
        next = cur.next;
        cur.next = reverseHead.next; ////将 cur 的next改成原链表的第一个
        reverseHead.next = cur; //将 cur 连接到新的链表上
        cur = next; //让 cur 后移
    }
    //将 head.next 指向 reverseHead.next 
     head.next = reverseHead.next;
}

从尾到头打印单链表

方式 1：反向遍历（即反转+遍历即可，上面已经写过）

方式 2：Stack 栈

public static void reversePrint(HeroNode head) {
    if (head.next == null) {
        return;
    }
    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = head.next;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}