链表，由若干个结点组成，每个结点包含数据域和指针域。结点结构如下图所示：
一般来讲，链表中只会有一个结点的指针域为空，该结点为尾结点，其他结点的指针域都会存储一个结点的内存地址。链表中也只会有一个结点的内存地址没有存储在其他结点的指针域，该结点称为头结点。
创建链表
定义了一个结构体Node，包含一个整数类型的data和一个指向下一个节点的指针next
typedef struct Node {int data;struct Node* next;
} Node;-
createNode函数用于创建一个新的节点，并初始化其数据和下一个节点指针。
//int data：表示要存储在新节点中的数据。
//返回值 函数返回一个指向新创建的 Node 结构体的指针。
Node* createNode(int data) {
//使用 malloc 函数分配一块内存，大小为 sizeof(Node)，即 Node 结构体的大小。
//(Node*) 将 malloc 返回的 void* 类型转换为 Node* 类型。Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("Memory allocation failed.\n");exit(1);}newNode->data = data;
//将新节点的 next 指针设置为 NULL，表示这个节点目前没有指向任何其他节点。newNode->next = NULL;return newNode;
}插入节点
链表的存储方式使得它可以高效的在指定位置插入与删除，时间复杂度均为 O(1)。
在结点 p 之后增加一个结点 q 总共分三步：
1.申请一段内存用以存储 q (可以使用内存池避免频繁申请和销毁内存)。
2.将 p 的指针域数据复制到 q 的指针域。
3.更新 p 的指针域为 q 的地址。
// 在 p 结点后面插入元素 q
void insertAfter(Node* p, int data) {if (p == NULL) {// 如果 p 是 NULL，无法插入，可能需要处理这种情况，例如返回错误或创建新链表printf("The given node p is NULL, cannot insert after it.\n");return;}// 1. 申请一段内存用以存储 qNode* q = createNode(data);// 2. 将 p 的指针域数据复制到 q 的指针域（在这里，我们只需要设置 q 的 next 为 p 的 next）q->next = p->next;// 3. 更新 p 的指针域为 q 的地址p->next = q;
}
删除节点
删除结点 p 之后的结点 q 总共分两步：
- 将 q 的指针域复制到 p 的指针域。
- 释放 q 结点的内存。
void removeAfter(Node* p) {if (p == NULL || p->next == NULL) {// 如果 p 是 NULL 或者 p 后面没有节点，不需要删除return;}// 将 q 的指针域复制到 p 的指针域Node* q = p->next;p->next = q->next;// 释放 q 结点的内存free(q);
}如何获取倒数第k个元素？（双指针）
先来看"倒数第k个元素的问题"。设有两个指针 p 和 q，初始时均指向头结点。首先，先让 p 沿着 next 移动 k 次。此时，p 指向第 k+1个结点，q 指向头节点，两个指针的距离为 k 。然后，同时移动 p 和 q，直到 p 指向空，此时 q 即指向倒数第 k 个结点。可以参考下图来理解：
// 找到链表中倒数第k个节点
Node* getKthFromEnd(Node* head, int k) {Node *p = head, *q = head;// 将 p指针移动 k 次for (int i = 0; i < k; ++i) {if (p == NULL) {return NULL; // 如果k大于链表长度，返回NULL}p = p->next;}// 同时移动 p 和 q，直到 p 到达链表末尾while (p != NULL) {p = p->next;q = q->next;}return q; // q 指向的就是倒数第 k 个节点
}// 释放链表内存
void freeList(Node* head) {Node* temp;while (head != NULL) {temp = head;head = head->next;free(temp);}
}获取中间位置元素
设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次，直到 fast 无法向后走两次。这使得在每轮移动之后。fast 和 slow 的距离就会增加一。设链表有 n 个元素，那么最多移动 n/2 轮。当 n 为奇数时，slow 恰好指向中间结点，当 n 为 偶数时，slow 恰好指向中间两个结点的靠前一个
class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode *p = head, *q = head;while(q != nullptr && q->next != nullptr) {p = p->next;q = q->next->next;}return p;}
};判断链表是否存在环
如果将尾结点的 next 指针指向其他任意一个结点，那么链表就存在了一个环。
当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的。当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *slow = head;ListNode *fast = head;while(fast != nullptr) {fast = fast->next;if(fast != nullptr) {fast = fast->next;}if(fast == slow) {return true;}slow = slow->next;}return nullptr;}
};判断环的长度
如何判断环的长度呢？方法是，快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度。
// 函数用于检测链表是否有环，并返回环的长度
int detectCycleLength(ListNode* head) {ListNode *fast = head, *slow = head;// 检测是否有环while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) { // 快慢指针相遇，存在环// 重置慢指针到头节点，快指针指向相遇点slow = head;while (slow != fast) {slow = slow->next;fast = fast->next;}// 计算环的长度int length = 1;fast = fast->next;while (slow != fast) {fast = fast->next;length++;}return length;}}return 0; // 无环
}
