链表的基础知识

  • 链表节点需存储值和一个next指针,所以在相同数据量下,链表比数组占用更多空间;
  • 在链表中插入/删除元素的时间复杂度为O(1)O(1)
  • 在链表中访问/查找元素的时间复杂度为O(n)O(n)

链表与数组

对比项 数组 链表
存储方式 连续的内存空间 非连续的内存空间,通过节点的指针连接
随机访问 支持随机访问,可以通过下标在 O(1)O(1) 时间内访问任意元素 不支持随机访问,访问特定元素需要从链表头开始遍历,时间复杂度为 O(n)O(n)
插入/删除操作 在中间位置插入或删除元素时,需要移动大量元素,时间复杂度为 O(n)O(n) 只需要修改指针,时间复杂度为 O(1)O(1)(在已知节点位置的情况下)
内存分配 分配连续的大块内存,可能会出现内存不足导致分配失败的情况 按需分配内存,较为灵活
内存开销 除了存储数据本身,只需要少量额外的空间记录数组长度等信息 每个节点都需要额外的空间存储指针,内存开销相对较大
适用场景 适合频繁随机访问,元素数量相对固定的场景 适合频繁插入、删除操作,元素数量动态变化较大的场景

链表结构

设计链表

设计链表包含这些关键元素:链表节点(值和next指针)、初始化构造函数、访问、插入、删除、遍历方法。

测试通过代码:

#include<iostream>

class MyLinkedList {

public:

    struct LinkedNode {
        int val;
        LinkedNode* next;

        LinkedNode() : val(0), next(nullptr) {};
        LinkedNode(int _val) :val(_val), next(nullptr) {};
    };

    MyLinkedList() {
        this->_dummyHead = new LinkedNode();
        this->_size = 0;
    }

    int get(int index) {
        if (index < 0 || index > _size - 1) {
            return -1;
        }

        LinkedNode* cur = _dummyHead->next;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }

    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);

        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        
        cur->next = newNode;
        _size++;
    }

    void addAtIndex(int index, int val) {
        if (index < 0 || index > _size) {
            return;
        }

        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while (index--) {
            cur = cur->next;
            std::cout <<"index = " << index << "cur->val =  " << cur->val<<std::endl;
        }

        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index > _size - 1) {
            return;
        }

        LinkedNode* cur = _dummyHead;
        while (index--) {
            cur = cur->next;
        }
        
        cur->next = cur->next->next;
        _size--;
    }

    void printLinkedList() {
        LinkedNode* cur = _dummyHead->next;

        while (cur) {
            std::cout << cur->val << " ";
            cur = cur->next;
        }
        std::cout << std::endl;
        std::cout << "size:" << _size << std::endl;
    }
private:
    LinkedNode* _dummyHead;
    int _size;
};

常见链表结构

除了单链表外,还有两种常见的链表类型:

  • 环形链表:链表的尾节点指向它的头节点,即可得到一个环形链表;在环形链表中,任意节点都可以被视为头节点;
  • 双向链表:不同于单链表,双向链表中还放有它前驱节点的pre指针,其遍历灵活性更强,但占用空间也更多。

常考题型

链表成环

力扣142. 环形链表 II - 力扣(LeetCode)

难度:中等

考察重点

  1. 确认链表是否成环;
  2. 快指针追上慢指针的原理;
  3. 找到链表环的入口;
  4. 寻找入口过程中三个指针走过的路程涉及的数学关系。

合并链表

力扣21. 合并两个有序链表 - 力扣(LeetCode)

难度:简单

考察重点

  1. 双指针;
  2. 虚拟头节点;
  3. 递归或迭代。

拓展(困难)23. 合并 K 个升序链表 - 力扣(LeetCode)