Welcome

0%

数据结构--链表总结

发表于 分类于

链表

链表的定义及优缺点：

来自维基百科

定义

链表（Linked list）是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。

链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个或下一个节点的位置的链接（”links”）。

优缺点

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

单链表

单链表的节点结构

1
2
3
4
5
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

单链表的设计实现

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class MyLinkedList {
public:
    /** Initialize your data structure here. */
    MyLinkedList() : list_size(0), tail(nullptr) {
        dummy = new ListNode(NULL);
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        if (index < 0 || index >= list_size) return -1;
        ListNode* cur = dummy->next;  //存储当前节点（从0开始）
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void addAtHead(int val) {
        ListNode* node = new ListNode(val);
        node->next = dummy->next;
        dummy->next = node;
        list_size++;  //节点数自增
        if (tail == nullptr)  //链表为空时先插入头节点
            tail = node;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        ListNode* node = new ListNode(val);
        if (tail == nullptr) {  //tail指针为空，说明当前链表为空（list_size = 0）
            tail = dummy;
        }
        tail->next = node;  //添加新节点到链表末尾
        tail = node;  //tail指向最后一个节点
        list_size++;  //节点数自增
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void addAtIndex(int index, int val) {
        if (index > list_size || index < 0) return;
        if (index == 0)  //在链表头部插入
            addAtHead(val);
        else if (index == list_size)  //在链表尾部插入
            addAtTail(val);
        else {
            ListNode* node = new ListNode(val);
            ListNode* pre = dummy;  //存储待插入节点的前一个节点
            while (index--) {
                pre = pre->next;
            }
            node->next = pre->next;  //待插入节点指向下一个节点
            pre->next = node;  //待插入节点的前一个节点指向待插入节点
            list_size++;  //链表长度自增
        }
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if (index >= list_size || index < 0) return;
        ListNode* pre = dummy;  //存储待删除节点的前一个节点
        while (index--) {
            pre = pre->next;
        }
        ListNode* cur = pre->next;  //暂存待删除的节点
        if (cur->next == nullptr) tail = pre;  //若待删除的为最后一个节点，尾指针前移
        pre->next = cur->next;  //待删除节点的前一个节点指向待删除节点的下一个节点，不用区分是否为最后一个节点
        list_size--;  //链表长度自减
        delete cur;  //释放已删除的节点空间，注意，其他指向该节点的指针的内容也没了
        cur = nullptr;
    }

private:
    int list_size;  //记录链表长度
    ListNode* dummy;  //添加头节点，便于处理
    ListNode* tail;  //指向链表的头指针
};

链表题目总结

题目分类

长度的游戏

多用快慢指针来实现，因为 2X-X = △k， 即X=△k，找到△k的意义，再在慢指针x上面接着做文章即可。举例 ： “链表中倒数第k个结点”，“两个链表的第一个公共结点”，“链表中环的入口结点”

指针的游戏

多加几个指针来解决问题（优先），也可以用vector等容器来装。举例： “反转链表”，“合并两个排序的链表”，“复杂链表的复制”，“删除链表中重复的节点”

典型例题

题目 考点
面试题22. 链表中倒数第k个节点 定义快慢节点指针，快的先走k步，然后两指针同步前进，待快指针到达尾后节点时，慢指针所指即为所得。
两个链表的第一个公共结点 长度的游戏：list1与list2的长度差很关键。先让长的走△步，然后一起遍历，第一个相同的就是要找的；时间复杂度 O(n+m)
链表中环的入口结点 快慢指针，两次相遇（第一次相遇之后，一个节点回到头节点，再次相遇点即为入口点）
206. 反转链表 可以用一个容器来装链表的每个节点，再反向构建链表，但这不是最佳思路；尝试多加链表的节点指针来解决。
合并两个排序的链表 非递归方法：使用三个指针，根据两个链表的当前节点大小依次追加；
递归方法：根据当前节点大小递归追加。
复杂链表的赋值 先复制每一个结点，插入到原节点后边，拼成一个长链表，再拆分
删除链表中重复的节点 1. 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况；
2. 设置 pre ，last 指针， pre指针指向当前确定不重复的那个节点，而last指针相当于工作指针，一直往后面搜索。
面试题06. 从尾到头打印链表 辅助栈，遍历入栈，出栈打印

参考链接：

基础数据结构：【动画】如何轻松手写链表？

力扣刷题总结之链表

祝大哥的博客：牛客网 > leetcode > 链表算法 题目总结