基本概念

链表（Linked List）是一种常见的数据结构，用于存储一系列的节点（Node），每个节点包含数据和指向下一个节点的指针。链表中的节点按照其在链表中的位置逐个连接，形成链式结构。

链表中的节点通常包含两个部分：

  1. 数据域（Data）：存储节点的数据。
  2. 指针域（Pointer）：指向下一个节点的指针，也可以称为“后继指针”（Next Pointer）。

链表可以分为多种类型，包括单向链表、双向链表和循环链表等。其中：

  • 单向链表（Singly Linked List）：每个节点只包含一个后继指针，指向下一个节点，形成一个单向的链式结构。
  • 双向链表（Doubly Linked List）：每个节点包含一个前驱指针（Previous Pointer）和一个后继指针，可以同时向前和向后遍历。
  • 循环链表（Circular Linked List）：链表中的最后一个节点的后继指针指向链表的头部，形成一个循环。

链表相比于数组有一些优点和缺点：

优点：

  • 动态性：链表的长度可以动态地增加或减少，不需要预先定义大小。
  • 灵活性：链表的节点可以在任意位置插入或删除，而数组需要进行元素的移动。
  • 空间利用：链表可以节省内存空间，因为节点只需额外存储数据和指针，而数组需要预留一段连续的内存空间。

缺点：

  • 随机访问性：链表的节点之间是通过指针连接的，因此不支持像数组那样的随机访问，需要从头节点开始顺序遍历。
  • 存储空间：链表需要额外存储指针信息，占用相对较多的存储空间。
  • 链表常常用于解决需要频繁的插入、删除操作，并且不需要随机访问的场景，如实现栈、队列、LRU 缓存等数据结构和算法问题。

经典题目

  1. 反转链表（Reverse Linked List）：反转一个单链表。
  2. 合并两个有序链表（Merge Two Sorted Lists）：合并两个有序链表，返回一个新的有序链表。
  3. 删除链表的倒数第 N 个节点（Remove Nth Node From End of List）：删除链表中倒数第 n 个节点。
  4. 判断链表是否有环（Linked List Cycle）：判断一个链表是否包含环。
  5. 相交链表（Intersection of Two Linked Lists）：找到两个链表相交的节点。
  6. 回文链表（Palindrome Linked List）：判断一个链表是否是回文链表。
  7. 环形链表 II（Linked List Cycle II）：找到一个链表中环的入口节点。
  8. 旋转链表（Rotate List）：将链表向右旋转 k 个位置。
  9. 排序链表（Sort List）：对链表进行排序。
  10. 删除排序链表中的重复元素（Remove Duplicates from Sorted List）：删除排序链表中的重复元素。

141.环形链表

November 30, 20221 分钟阅读 Liubang LeetCode LeetCodeLinkedList

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。

解法一：hash 法

hash 法是我们在判断重复元素类问题中最常用的方法。针对链表是否有环来说，我们可以遍历链表，并用std::set 存放遍历过的元素，判断是否存在重复元素，如果存在则表示有环，如果遍历结束且不存在重复，则没有环。...

206.反转链表

November 30, 20221 分钟阅读 Liubang LeetCode LeetCodeLinkedList

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解法一：迭代

迭代法应该是我们最容易想到的常规方法，也比较符合人的思维逻辑。其核心思想就是通过两个指针移动，来 一个一个的修改链表的指向方向。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur) {...

24.两两交换链表中的节点

November 30, 20221 分钟阅读 Liubang LeetCode LeetCodeLinkedList

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

方法一：递归

这道题，最最简洁的方法应该就是使用递归了。主要思路是，每两个一组，进行交换，然后递归执行。

class Solution {
public:
    LinkedList* swapPairs(LinkedList* head) {
        if (!head || !head->next) return head;
        // 当前组下的新的head
        LinkedList* newHead = head->next;...