leetcode-代码随想录-链表-链表理论基础

链表：

• 通过指针串联在一起的线性结构；
• 每个节点包含两部分：数据域、指针域（存放下一个节点的指针）
• 入口节点：称为 头节点 head
• 最后一个节点的指针指向 NULL（空指针）

链表的类型

1. 单链表（Singly Linked List）

• 结构：每个节点包含数据域和指向下一个节点的指针（next）。
• 特点：
  • 单向遍历，只能从头节点开始逐个访问。
  • 插入/删除节点的时间复杂度为 O(1)（已知前驱节点时）。
  • 查找时间复杂度为 O(n)。
• 缺点：- 无法逆向遍历，删除节点需要从头查找前驱节点。
• 应用场景：简单队列、不需要反向操作的场景。

2. 双向链表（Doubly Linked List）

• 结构：每个节点包含数据域、前驱指针（prev）和后继指针（next）。
• 特点：
  • 支持双向遍历（正向和逆向）。
  • 插入/删除节点的时间复杂度为 O(1)（已知目标节点时）。
• 缺点：- 每个节点多占用一个指针的空间。
• 应用场景：需要双向操作的场景（如浏览器历史记录、撤销/重做功能）。
  

3. 循环链表（Circular Linked List）

• 结构：链表首尾相连，形成闭环。
• 类型：
  • 单循环链表：尾节点指向头节点，只能单向循环遍历。
  • 双循环链表：头尾节点互相连接，支持双向循环遍历。
• 特点：
  • 从任意节点出发均可遍历整个链表。
  • 适合周期性操作。
• 应用场景：轮询任务调度、约瑟夫环问题。
  

链表的存储

• 数组：连续分布
• 链表：不连续的，分布在内存的不同地址空间上，通过指针串联在一起

链表相关代码

定义

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

输出链表

void printLinkedList(ListNode* head){
    ListNode* cur = head;
    while(cur != nullptr) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

通过输入 - 创建单链表

int main() {
    
    int n, m;
    ListNode* dummyHead = new ListNode(0);
    while(cin >> n){
        if(n == 0){
            cout << "list is empty" << endl;
            continue;
        }

        ListNode* cur = dummyHead;
        while(n--){
            cin >> m;
            ListNode* newNode = new ListNode(m);
            cur->next = newNode;
            cur = cur->next;
        }
    }

    ListNode* head = dummyHead->next;
    printLinkedList(head);
}

直接创建单链表

    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(6);