链表是一种常见的基础数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。相比于数组,链表在插入和删除操作上更加灵活,但同时也需要更多的内存空间来存储指针。本文将详细解析链表数据结构,并介绍几种常见的链表算法实现技巧。
链表的基本概念
节点结构
链表中的每个节点包含两部分:数据和指针。数据部分存储实际的数据值,指针部分存储指向下一个节点的地址。
struct ListNode {
int val;
struct ListNode *next;
};
链表类型
- 单向链表:每个节点只有一个指向下一个节点的指针。
- 双向链表:每个节点包含两个指针,一个指向前一个节点,一个指向下一个节点。
- 循环链表:最后一个节点的指针指向链表的第一个节点,形成一个循环。
链表操作
创建链表
创建链表需要先定义节点结构,然后动态分配内存,并设置指针。
struct ListNode* createList(int n) {
struct ListNode *head = NULL, *pre = NULL, *temp = NULL;
for (int i = 0; i < n; i++) {
temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = i;
temp->next = NULL;
if (pre) {
pre->next = temp;
} else {
head = temp;
}
pre = temp;
}
return head;
}
插入节点
插入节点分为头插法、尾插法和指定位置插入。
// 头插法
void insertHead(struct ListNode *head, int val) {
struct ListNode *temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = val;
temp->next = head;
head = temp;
}
// 尾插法
void insertTail(struct ListNode *head, int val) {
struct ListNode *temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = val;
temp->next = NULL;
if (head == NULL) {
head = temp;
} else {
struct ListNode *pre = head;
while (pre->next) {
pre = pre->next;
}
pre->next = temp;
}
}
// 指定位置插入
void insertPos(struct ListNode *head, int pos, int val) {
struct ListNode *temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = val;
if (pos == 0) {
temp->next = head;
head = temp;
} else {
struct ListNode *pre = head;
for (int i = 0; i < pos - 1; i++) {
if (pre == NULL) {
return;
}
pre = pre->next;
}
temp->next = pre->next;
pre->next = temp;
}
}
删除节点
删除节点分为删除头节点、删除尾节点和指定位置删除。
// 删除头节点
void deleteHead(struct ListNode *head) {
if (head == NULL) {
return;
}
struct ListNode *temp = head;
head = head->next;
free(temp);
}
// 删除尾节点
void deleteTail(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return;
}
struct ListNode *pre = head;
while (pre->next->next) {
pre = pre->next;
}
free(pre->next);
pre->next = NULL;
}
// 指定位置删除
void deletePos(struct ListNode *head, int pos) {
if (head == NULL) {
return;
}
if (pos == 0) {
deleteHead(head);
} else {
struct ListNode *pre = head;
for (int i = 0; i < pos - 1; i++) {
if (pre == NULL) {
return;
}
pre = pre->next;
}
if (pre->next == NULL) {
return;
}
struct ListNode *temp = pre->next;
pre->next = temp->next;
free(temp);
}
}
遍历链表
遍历链表是链表操作中最基本的操作,可以通过循环遍历每个节点来访问链表中的数据。
void traverseList(struct ListNode *head) {
struct ListNode *temp = head;
while (temp) {
printf("%d ", temp->val);
temp = temp->next;
}
printf("\n");
}
链表算法实现技巧
查找倒数第k个节点
struct ListNode* findKthToTail(struct ListNode *head, int k) {
struct ListNode *fast = head, *slow = head;
for (int i = 0; i < k; i++) {
if (fast == NULL) {
return NULL;
}
fast = fast->next;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
合并两个有序链表
struct ListNode* merge(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
free(dummy);
return cur->next;
}
反转链表
struct ListNode* reverseList(struct ListNode *head) {
struct ListNode *pre = NULL, *cur = head, *next = NULL;
while (cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
删除链表的中间节点
void deleteNode(struct ListNode *node) {
node->val = node->next->val;
node->next = node->next->next;
}
总结
链表是一种重要的数据结构,它在很多算法中都有应用。本文详细介绍了链表的基本概念、操作和常见算法实现技巧。通过学习和掌握链表,可以帮助我们更好地理解和解决各种编程问题。
