算法通关村第一关——链表青铜挑战笔记

本文最后更新于：9 个月前

20230911

1 什么是链表

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。

1.1 单向链表

单向链表的每一个节点又包含两部分，一部分是存放数据的变量 data ，另一部分是指向下一个节点的指针next。

image-20230911214122465

链表的第1个节点被称为头节点，最后1个节点被称为尾节点，尾节点的 next 指针指向空。

1.2 双向链表

双向链表的每一个节点除了拥有 data 和 next 指针，还拥有指向前置节点的 prev 指针。

image-20230911214337432

1.3 链表的存储方式

链表在内存中的存储方式是随机存储。链表采用了见缝插针的方式，链表的每一个节点分布在内存的不同位置，依靠 next 指针关联起来。这样可以灵活有效地利用零散的碎片空间。

image-20230911214538218

图中的箭头代表链表节点的 next 指针。

1.4 链表概念补充

1.4.1 链表

使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。

链表存储数据间逻辑关系的实现方案是:为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素，也就是下图所示的样子。

image-20230911214855519

像上图这样，数据元素随机存储在内存中，通过指针维系数据之间“一对一”的逻辑关系，这样的存储结构就是链表。

1.4.2 节点和头节点

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

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

1.4.3 虚拟节点

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

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

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

2 创建链表

首先要理解 JVM 是怎么构建出链表的，JVM 里有栈区和堆区，栈区主要存引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象

假如这样定义一个类：

1
2
3
4
public class Course{
    int val;
    Course next;
}

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

image-20230911220233877

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

从 head 开始 next 会发现是这样的:

image-20230911220450363

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

根据面向对象的理论，在 Java 里规范的链表应该这么定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

但是在算法中经常使用这样的方式来创建链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
        next = null;
    }

    public static void main(String[] args) {
        ListNode listnode=new ListNode(1);
    }
}

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

3 链表的基本操作

对于单链表，不管进行什么操作，一定是从头开始逐个向后访问，所以操作之后是否还能找到表头非常重要。

一定要注意”狗熊掰棒子”问题（掰一个扔一个），也就是只顾当前位置而将标记表头的指针丢掉了。

image-20230911214855519

遍历链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
     * 获取链表长度
     *
     * @param head 链表头节点
     * @return 链表长度
     */
    public static int getLength(Node head) {
        int length = 0;
        Node node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

3.1 查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。

例如：给出一个链表，需要查找从头节点开始的第3个节点。

image-20230911222837880

查找链表节点的时间复杂度是多少？

链表中的数据只能按顺序进行访问，最坏的时间复杂度是 O(n)

3.2 更新节点

如果不考虑查找节点的过程，链表的更新过程直接把旧数据替换成新数据即可。

image-20230911222316455

3.3 插入节点

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

3.3.1 头部插入

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

image-20230911223058734

3.3.2 中间插入

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

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

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

image-20230911223642343

思考：为什么不能颠倒顺序?
由于每个节点都只有一个next，因此执行了node(15).next=new之后，结点15和7之间的连线就自动断开了，如上图所示。

3.3.3 尾部插入

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。

image-20230911223930152

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

综上所述，链表插入方法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 /**
     * 链表插入
     *
     * @param head       链表头节点
     * @param nodeInsert 待插入节点
     * @param position   待插入位置，取值从2开始
     * @return 插入后得到的链表头节点
     */
    public static Node insertNode(Node head, Node nodeInsert, int position) {
        // 需要判空，否则后面可能会有空指针异常
        if (head == null) {
            return nodeInsert;
        }
        //越界判断
        int size = getLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;
        }

        //在链表开头插入
        if (position == 1) {
            nodeInsert.next = head;
//            return nodeInsert;
            //上面return还可以这么写：
            head = nodeInsert;
            return head;
        }

        Node pNode = head;
        int count = 1;
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;

        return head;
    }

补充：head = null 的时候该执行什么操作呢?

如果是 null 的话，你要插入的结点就是链表的头结点，也可以直接抛出不能插入的异常，两种处理都可以，一般来说我们更倾向前者。

3.4 删除元素

链表的删除操作同样分为3种情况。

3.4.1 头部删除

删除表头元素还是比较简单的，一般只要执行 head=head.next 就行了。如下图，将 head 向前移动一次之后，原来的结点不可达，会被 JVM 回收掉。

image-20230911225429004

3.4.2 尾部删除

删除的过程不算复杂，也是找到要删除的结点的前驱结点，这里同样要在提前一个位置判断，例如下图中删除 40，其前驱结点为 7。遍历的时候需要判断 cur.next 是否为 40，如果是，则只要执行 cur.next=null 即可，此时结点 40 变得不可达，最终会被 JVM 回收掉。

image-20230911225457084

3.4.3 中间删除

删除中间结点时，也会要用 cur.next 来比较，找到位置后，将 cur.next 指针的值更新为 cur.next.next 就可以解决，如下图所示:

image-20230911225649306

综上所述，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
     * 删除节点
     *
     * @param head     链表头节点
     * @param position 删除节点位置，取值从1开始
     * @return 删除后的链表头节点
     */
    public static Node deleteNode(Node head, int position) {
        if (head == null) {
            return null;
        }
        int size = getLength(head);
        //思考一下，这里为什么是size，而不是size+1
        if (position > size || position <1) {
            System.out.println("输入的参数有误");
            return head;
        }
        if (position == 1) {
            //curNode就是链表的新head
            return head.next;
        } else {
            Node cur = head;
            int count = 1;
            while (count < position - 1) {
                cur = cur.next;
                count++;
            }
            Node curNode = cur.next;
            cur.next = curNode.next;
        }
        return head;
    }

4 思考一下

4.1 题一

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

图一：

image-20230911230028715

图二：

image-20230911230215982

解析：上面第一个图是满足单链表要求的，因为我们说链表要求环环相扣，核心是一个结点只能有一个后继，但不代表个结点只能有一个被指向。

第一个图中，c1被a2和b3同时指向，这是没关系的。这就好比法律倡导一夫一妻，你只能爱一个人，但是可以都多个人爱你。

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

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

image-20230911230352038

4.2 题二

如果链表是单调递增的，一般会让你将元素插入到合适的位置，序列仍然保持单调，你可以尝试写一下该如何实现。

4.3 题三

同样，在很多算法中链表是单调的，让你在删除元素之后仍然保持单调，建议写一下试试。

CSDN 发布文章

文章链接：https://blog.csdn.net/weixin_45876773/article/details/132819449

1 理解Java是如何构造出链表的？

首先要理解 JVM 是怎么构建出链表的，JVM 里有栈区和堆区，栈区主要存引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象

假如这样定义一个类：

1
2
3
4
public class Course{
    int val;
    Course next;
}

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

image-20230911220233877

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

从 head 开始 next 会发现是这样的:

image-20230911220450363

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

根据面向对象的理论，在 Java 里规范的链表应该这么定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

但是在算法中经常使用这样的方式来创建链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
        next = null;
    }

    public static void main(String[] args) {
        ListNode listnode=new ListNode(1);
    }
}

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

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

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

2.1 头部插入

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

image-20230911223058734

2.2 中间插入

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

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

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

image-20230911223642343

思考：为什么不能颠倒顺序?
由于每个节点都只有一个next，因此执行了node(15).next=new之后，结点15和7之间的连线就自动断开了，如上图所示。

2.3 尾部插入

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。

image-20230911223930152

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

综上所述，链表插入方法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 /**
     * 链表插入
     *
     * @param head       链表头节点
     * @param nodeInsert 待插入节点
     * @param position   待插入位置，取值从2开始
     * @return 插入后得到的链表头节点
     */
    public static Node insertNode(Node head, Node nodeInsert, int position) {
        // 需要判空，否则后面可能会有空指针异常
        if (head == null) {
            return nodeInsert;
        }
        //越界判断
        int size = getLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;
        }

        //在链表开头插入
        if (position == 1) {
            nodeInsert.next = head;
//            return nodeInsert;
            //上面return还可以这么写：
            head = nodeInsert;
            return head;
        }

        Node pNode = head;
        int count = 1;
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;

        return head;
    }

补充：head = null 的时候该执行什么操作呢?

如果是 null 的话，你要插入的结点就是链表的头结点，也可以直接抛出不能插入的异常，两种处理都可以，一般来说我们更倾向前者。

3 链表删除元素，首部、中间和尾部分别会有什么问题，该如何处理?

链表的删除操作同样分为3种情况。

3.1 头部删除

删除表头元素还是比较简单的，一般只要执行 head=head.next 就行了。如下图，将 head 向前移动一次之后，原来的结点不可达，会被 JVM 回收掉。

image-20230911225429004

3.2 尾部删除

删除的过程不算复杂，也是找到要删除的结点的前驱结点，这里同样要在提前一个位置判断，例如下图中删除 40，其前驱结点为 7。遍历的时候需要判断 cur.next 是否为 40，如果是，则只要执行 cur.next=null 即可，此时结点 40 变得不可达，最终会被 JVM 回收掉。

image-20230911225457084

3.3 中间删除

删除中间结点时，也会要用 cur.next 来比较，找到位置后，将 cur.next 指针的值更新为 cur.next.next 就可以解决，如下图所示:

image-20230911225649306

综上所述，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
     * 删除节点
     *
     * @param head     链表头节点
     * @param position 删除节点位置，取值从1开始
     * @return 删除后的链表头节点
     */
    public static Node deleteNode(Node head, int position) {
        if (head == null) {
            return null;
        }
        int size = getLength(head);
        //思考一下，这里为什么是size，而不是size+1
        if (position > size || position <1) {
            System.out.println("输入的参数有误");
            return head;
        }
        if (position == 1) {
            //curNode就是链表的新head
            return head.next;
        } else {
            Node cur = head;
            int count = 1;
            while (count < position - 1) {
                cur = cur.next;
                count++;
            }
            Node curNode = cur.next;
            cur.next = curNode.next;
        }
        return head;
    }

4 双向链表是如何构造的，如何实现元素的插入和删除？

双向链表的每一个节点除了拥有 data 和 next 指针，还拥有指向前置节点的 prev 指针。

image-20230911214337432

双向链表的一个基本实现通常需要节点类（Node）和双向链表类（DoublyLinkedList）。节点类存储数据和指向前一个以及后一个节点的指针。双向链表类包含指向链表头部的指针，以及管理链表的各种方法，例如插入节点和删除节点。

双向链表实现示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    Node head;

    // 插入节点到链表的末尾
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            Node newNode = new Node(data);
            current.next = newNode;
            newNode.prev = current;
        }
    }

    // 删除指定数据的节点
    public void delete(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                    if (current.next != null) {
                        current.next.prev = current.prev;
                    }
                } else {
                    head = current.next;
                    if (current.next != null) {
                        current.next.prev = null;
                    }
                }
                return;
            }
            current = current.next;
        }
    }

    // 打印链表的所有元素
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }
}

在这个例子中，append 方法在链表的末尾添加一个新的节点，delete 方法删除具有指定数据的节点，而 printList 方法打印出链表的所有元素。

算法通关村
#链表
算法通关村第一关——链表青铜挑战笔记
http://example.com/2023/09/11/算法通关村第一关——链表青铜挑战笔记/
作者
crush
发布于
2023年9月11日
更新于
2023年9月12日
许可协议