第 1 关 | 原来链表这么有用 : 1.青铜挑战——小白也能学会链表-灵析社区

1. 单链表的概念

首先看一下什么是链表，单向链表就如同铁链一样，元素之间相互连接，包含多个结点，每个节点有一个指向后继元素的 next 指针。表中最后一个元素的 next 指向 null。如下图：

思考一下

你是否理解了链表的含义，思考一下下面两个图，是否都满足单链表的要求，为什么？

第一个图：

第二个图：

解析：

上面第一个图是满足单链表的要求的，因为我们说链表要求环环相扣，核心是一个结点只能有一个后继，但是不代表一个结点只能有一个被指向。第一个图中，c1 被 a2 和 b3 同时指向，这是没关系的。这就好比法律倡导一夫一妻的制度，但是你只能爱一个人，但是可以多个人同时爱你。

第二个图就不满足要求了，因为 c1 有两个后继 a5 和 b4。

另外再做题的时候比较要注意的是值还是结点，因为有时候两个结点的值可能相等，但是并不是同一个结点，例如下图中，有两个结点的值都是 1，但并不是同一个结点。

2. 链表的相关概念

节点和头节点

在链表中，每个点都由值和指向下一个结点的地址组成的独立的单元，称为一个结点，有时候也称为节点，含义都是一样的。

对于单链表，如果知道了第一个元素，就可以通过遍历访问整个链表，因此第一个结点最重要，一般称为头结点。

虚拟节点

在做题以及在工程里面经常可以看到虚拟节点的概念，其实就是一个节点 dummyNode，其 next 指针指向 head，也就是 dummyNode.next=head。

因此，如果我们在算法里面使用了虚拟节点，则要注意如果获得 head 节点，或者从方法（函数）里返回的时候，应该使用 dummyNode.next。

另外注意，dummyNode 的 val 不会被使用，初始化 0 或者 -1 都是可以的，既然不会被使用，那么虚拟节点有什么作用呢？简单来说，就是为了方便我们处理头部节点，否则我们需要在代码里单独处理首部节点的问题，在链表反转里面，我们会看到该方式大大降低解题难度。

3. 创建链表

我们看如何构造链表。

首先，要理解 JVM 是如何构建出链表的，我们知道 JVM 里面有堆区以及栈区，栈区主要负责引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象，例如我们顶一个这样的类：

public class Course{
    Teacher teacher;
    Student student;
}

这里的 teacher 和 student 就是指向堆的引用，假如我们这样定义：

public class Course{
	int val;
    Course next;
}

这个时候 next 就指向了下一个同为 Course 类型的对象了，例如：

这样通过栈的引用（也就是地址），就可以找到 val （1），然后 val （1）节点又存了指向 val （2）的地址，然后 val （3）又存了指向 val （4）的地址，就这样，构造出了一个链表访问结构。

在 Java 配套代码中 BasicLink 类，我们 debug 一下看一下就会发现下图：

这样就是一个简单的线性访问了，所以链表就是从 head 开始，逐个开始向后访问，然后每次所访问对象的类型都是一样的。

根据面向对象的理论，在 Java 里面规范的链表定义如下：

public class LinkList {
    private int data;
    private LinkList next;

    public LinkList(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public LinkList getNext() {
        return next;
    }

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

但是在 LeetCode 中算法题中经常使用以下方式来创建链表：

public class ListNode{
	public int val;
    private ListNode next;

    ListNode (int x){
        this.val = x;
        this.next = null;
    }
}
ListNode listnode= new ListNode(1);

这里的 val 就是当前节点的值，next 指向下一个结点。因为两个变量都是 public 的，创建对象后能直接使用 listnode.val 和 listnode.next 来操作，虽然这样不满足面向对象的设计要求，但是代码更加精简。因此在算法题目中应用更加广泛。

4. 链表的增删改查

4.1. 链表遍历

对于单链表，不管进行什么操作，都要从头到后逐个访问，所以操作之后是否还能找到表头非常重要。一定要注意“狗熊掰棒子”问题，也就是只顾当前位置而将标记表头的指针丢掉了。

/**
 * 获取链表长度
 * @param head 链表的头结点
 * @return
 */
public static int getListLength(ListNode head){
    int length = 0;
    ListNode node = head;
    while(node != null){
        length++;
        node = node.next;
    }
    return length;
}

/**
     * 链表遍历打印
     * @param head
     */
    public static void printNodeList(ListNode head) {
        if(head == null) {
            System.out.println("链表为空，无法打印!");
            return;
        }
        int length = 0;
        //定义头结点
        ListNode node = head;
        while (node != null) {
            System.out.println(node.data);
            length++;
            node = node.next;
        }
    }

4.2. 链表插入

单链表的插入和数组的插入一样，分为三种情况，过程并不复杂，但是在编码的时候会发现都是坑。单链表的插入需要考虑三种操作：首部、中部和尾部。

4.2.1. 链表头插入

链表表头插入新节点非常简单，容易出错的是可能会经常忘记 head 需要重新指向表头，我们需要创建一个新节点 newNode，怎么连接到原来的链表呢？执行 newNode.next = head 就可以，之后我们要遍历新链表就要从 newNode 开始一路向下了是吧，但是我们海狮习惯用 head 来表示，所以让 head = newNode 就可以了，如下图：

4.2.2. 链表中间插入

在中间位置插入，首先遍历找到要插入的位置，然后当前位置接入到前驱节点和后继节点之间，但是到了还位置之后我们却不能获得前驱节点，也就无法将节点接入进来。这就好比一边过河一边拆桥，结果自己没办法回去了。

为此，我们要在目标节点前一个位置停下来，也就是使用 cur.next 的值来判断，而不是用 cur 的值来判断，这是链表常用的策略。

如下图，如果要在 7 前面插入，当 cur.next = node(7) 的时候就要停下来，此时 cur.val = 15,然后需要给newNode 前后接两根线，此时只能让 new.next = node(15).next(图中虚线)，然后 node（15）.next = new，而且顺序还不能出错。

为什么不能颠倒顺序呢？

由于每个节点都只有一个 next，因此执行了 node( 15) .next = new 之后，节点 15 和 7之间的连线就自动断开了，如下图所示：

4.2.3. 单链表尾部插入节点

表尾插入就比较容易了，我们只需要将尾部节点插入指向新节点就可以了。

public static ListNode insertNode(ListNode head, ListNode nodeInsert, int position) {
        // 头结点为空，直接返回
        if (head == null) {
            return nodeInsert;
        }
        // 已经存放的元素格式
        int size = getListLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;
        }

        //表头插入
        if (position == 1) {
            nodeInsert.next = head;
            //这里可以直接返回 nodeInsert,也可以先将头结点位置前移
            head = nodeInsert;
            return head;
        }
        // 定义一个临时节点用于遍历
        ListNode pNode = head;
        int count = 1;
        // 这里的 position 被 size 限制住，所以不用考虑 pNode = null
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }

        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;

        return head;
    }

这里补充一个点，如果 head = null 的时候，如果插入的节点是链表的头结点，也可以直接抛出不能插入的异常，两种处理都可以，一般来说我更加倾向于前者。

如果链表是单调递增的，一般会让你把元素插入到合适的地方，然后序列保持单调。

4.3. 链表删除

4.3.1. 删除链表头结点

执行head=head.next即可，如下图，将head向前移动一次后，原结点不可达，会被JVM回收。

4.3.2. 删除链表尾部节点

找到其前驱结点，令其指向null即可。例如下图，同样用cur.next = 40 找到其前驱结点，再执行cur.next=null即可，此时结点40不可达，被JVM回收。

4.3.3. 删除链表中间节点

同样用cur.next比较，找到位置后，将cur.next指针的值更新为cur.next.next即可。如下图：

/**
 * 删除节点
 *
 * @param head     链表头结点
 * @param position 删除节点位置，取值从 1 开始
 * @return 删除后的链表头结点
 */
public static ListNode deleteNode(ListNode head, int position) {
    //判断头结点是否为空，为空的话直接不删除
    if (head == null) {
        System.out.println("链表为空，无法删除！");
        return null;
    }
    int size = getListLength(head);
    // 删除的话一般都尾部节点就可以了，因为尾部节点的下一个节点为空，所以不需要删除
    if (position > size || position < 1) {
        System.out.println("输入参数有误!");
        return head;
    }
    if(position == 1){
        return head.next;
    }
    ListNode cur = head;
    int count = 1;
    while(count < position - 1){
        cur = cur.next;
        count++;
    }
    cur.next = cur.next.next;
    return  head;
}

5. 总结

5.1. 完整代码

package com.qinyao.linklist;


/**
 * @ClassName LinkList
 * @Description
 * @Version 1.0.0
 * @Author LinQi
 * @Date 2023/09/04
 */
public class ListNode {
    private int data;
    private ListNode next;

    public ListNode(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return next;
    }

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

    /**
     * 获取链表长度
     *
     * @param head 链表的头结点
     * @return
     */
    public static int getListLength(ListNode head) {
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    /**
     * 链表遍历打印
     *
     * @param head
     */
    public static void printNodeList(ListNode head) {
        if (head == null) {
            System.out.println("链表为空，无法打印!");
            return;
        }
        int length = 0;
        //定义头结点
        ListNode node = head;
        while (node != null) {
            System.out.println(node.data);
            length++;
            node = node.next;
        }
    }

    /**
     * 链表插入
     *
     * @param head       链表头结点
     * @param nodeInsert 待插入节点
     * @param position   待插入位置，从 1 开始
     * @return 插入后得到的链表头结点
     */
    public static ListNode insertNode(ListNode head, ListNode nodeInsert, int position) {
        // 头结点为空，直接返回
        if (head == null) {
            return nodeInsert;
        }
        // 已经存放的元素格式
        int size = getListLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;
        }

        //表头插入
        if (position == 1) {
            nodeInsert.next = head;
            //这里可以直接返回 nodeInsert,也可以先将头结点位置前移
            head = nodeInsert;
            return head;
        }
        // 定义一个临时节点用于遍历
        ListNode pNode = head;
        int count = 1;
        // 这里的 position 被 size 限制住，所以不用考虑 pNode = null
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }

        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;

        return head;
    }

    /**
     * 删除节点
     *
     * @param head     链表头结点
     * @param position 删除节点位置，取值从 1 开始
     * @return 删除后的链表头结点
     */
    public static ListNode deleteNode(ListNode head, int position) {
        //判断头结点是否为空，为空的话直接不删除
        if (head == null) {
            System.out.println("链表为空，无法删除！");
            return null;
        }
        int size = getListLength(head);
        // 删除的话一般都尾部节点就可以了，因为尾部节点的下一个节点为空，所以不需要删除
        if (position > size || position < 1) {
            System.out.println("输入参数有误!");
            return head;
        }
        if(position == 1){
            return head.next;
        }
        ListNode cur = head;
        int count = 1;
        while(count < position - 1){
            cur = cur.next;
            count++;
        }
        cur.next = cur.next.next;
        return  head;
    }
}

5.2. 思考

5.2.1. 如何构造链表？

构造链表的 data 以及 next 既可，data 用于存储链表的数据，next 用于指向下一个数据

5.2.2. 链表增加元素，首部、中间和尾部分别有什么问题，该如何处理？

首部：如果插入链表的时候，链表为空的时候，这个时候可以返回异常或者返回插入的节点就可以

中间：需要注意，需要遍历到插入的前一个节点就足够了，然后将链表对应位置的下一个节点先赋值给插入节点，然后链表的写一个节点指向插入节点既可

尾部：需要注意，如果索引大于链表元素 2 个，则表示插入错误。

5.2.3. 链表删除元素，首部、中间和尾部分别有什么问题。该如何处理？

首部：如果链表头部为空，无法删除

中间：删除的时候同插入，需要遍历到前一个节点

尾部：插入的时候需要注意索引位置