链表是一种常用的数据结构，它具有许多特点，比如动态性、添加/删除节点方便、灵活性强等特点。在本篇文章中，我们将从不同的角度来详细阐述链表的特点及其应用。
一、链表的定义
链表是一种线性数据结构，它由多个节点组成，每个节点包含两个部分，一个是数据域，用来存储数据，另一个是指针域，用来指向下一个节点的地址。链表的特点是不同于数组和其他数据结构的动态性，因为链表可以按需分配空间并且在运行时添加或删除元素，所以链表在很多场景下都非常适用。
二、链表的种类
链表主要有单向链表、双向链表和循环链表三种，它们在结构上略有不同，但都具备链表的基本特点。
1. 单向链表
单向链表是指每个节点只有指向下一节点的指针，不能回溯到前面的节点。
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
2. 双向链表
双向链表是指每个节点都有指向前面和后面节点的指针，可以在两个方向上遍历。
class ListNode {
public:
int val;
ListNode *prev;
ListNode *next;
ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};
3. 循环链表
循环链表是指最后一个节点的指针指向第一个节点，形成了一个环状结构。
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
三、链表的操作
1. 遍历链表
遍历链表是指依次访问链表中的所有节点，可以使用while循环或者递归方式实现。
void traverseList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
// 进行一些操作，比如输出节点值
cout <val <next;
}
}
2. 在链表中添加节点
添加节点是指在链表中插入一个新的节点，通常采用头插法和尾插法两种方式实现。
（1）头插法
在链表的头部插入一个新的节点。
ListNode* addAtHead(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
head = newNode;
return head;
}
（2）尾插法
在链表的尾部插入一个新的节点。
ListNode* addAtTail(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
if (head == NULL) {
head = newNode;
return head;
}
ListNode* p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = newNode;
return head;
}
3. 在链表中删除节点
删除节点是指删除链表中的一个节点，通常按节点值和节点位置来删除。
（1）按节点值删除
在链表中查找节点值等于给定值，然后删除该节点。
ListNode* deleteNode(ListNode* head, int val) {
if (head == NULL) {
return NULL;
}
ListNode* p = head;
if (head->val == val) {
head = head->next;
return head;
}
while (p->next != NULL && p->next->val != val) {
p = p->next;
}
if (p->next != NULL) {
p->next = p->next->next;
}
return head;
}
（2）按节点位置删除
在链表中根据节点位置来删除节点，通常需要保存要删除节点的前一个节点。
ListNode* deleteNode(ListNode* head, int pos) {
if (head == NULL) {
return NULL;
}
ListNode* p = head;
if (pos == 0) {
head = head->next;
return head;
}
for (int i = 0; i next != NULL; i++) {
p = p->next;
}
if (p->next != NULL) {
p->next = p->next->next;
}
return head;
}
四、链表的应用
链表广泛应用于各种数据结构和算法中，比如队列、栈、哈希表等。下面是链表应用的一些实际例子。
1. LRU缓存淘汰算法
LRU缓存淘汰算法是一种利用链表实现的缓存淘汰策略，当缓存满时，淘汰最近最少使用的节点。
class LRUCache {
private:
struct Node {
int key, val;
Node *next, *prev;
Node(int _key, int _val) : key(_key), val(_val), next(NULL), prev(NULL) {}
};
int _capacity;
Node *head, *tail;
public:
LRUCache(int capacity) : _capacity(capacity) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
Node *node = cache[key];
deleteNode(node);
addToHead(node);
return node->val;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
node->val = value;
deleteNode(node);
addToHead(node);
} else {
if (cache.size() == _capacity) {
Node *tailNode = tail->prev;
cache.erase(tailNode->key);
deleteNode(tailNode);
}
Node *node = new Node(key, value);
cache[key] = node;
addToHead(node);
}
}
void addToHead(Node *node) {
node->next = head->next;
head->next->prev = node;
head->next = node;
node->prev = head;
}
void deleteNode(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
};
2. 链表求解环形结构问题
链表求解环形结构问题是指判断链表中是否存在环状结构，并可以找出环状结构的入口节点。
ListNode* detectCycle(ListNode* head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
ListNode* fast = head, *slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
ListNode* p = head;
while (p != slow) {
p = p->next;
slow = slow->next;
}
return p;
}
}
return NULL;
}
3. 链表操作综合案例
下面是一个基于链表操作的综合案例，实现了链表的逆转、排序、合并、删除重复元素等操作。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
ListNode* sortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* slow = head, *fast = head->next;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next;
slow->next = NULL;
return merge(sortList(head), sortList(mid));
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummy(0), *p = &dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if (l1 != NULL) {
p->next = l1;
}
if (l2 != NULL) {
p->next = l2;
}
return dummy.next;
}
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) {
return NULL;
}
ListNode* p = head;
while (p->next != NULL) {
if (p->val == p->next->val) {
p->next = p->next->next;
} else {
p = p->next;
}
}
return head;
}
};
总结
链表是一种非常常用的数据结构，它具有许多特点，比如动态性、添加/删除节点方便、灵活性强等特点，而且在各种算法和数据结构的实现中广泛应用。在学习的过程中，我们需要熟练掌握链表的基本操作，理解不同种类的链表，并在实践中掌握链表的常见应用，提高算法和编程能力。