单链表综合练习
链表是 C 语言数据结构学习的核心考点,也是编程入门绕不开的经典题型。本文聚焦删除指定值节点、反转链表、查找中间节点三大高频链表题,从算法原理到代码实现逐层拆解,用通俗易懂的逻辑和清晰的代码示例,帮你吃透链表操作的核心思路。
一、删除链表中等于给定值 val 的所有节点
1.1 题目描述
给定一个链表的头节点 head 和一个整数 val,请删除链表中所有满足 node.val == val 的节点,并返回新的头节点。
1.2 思路解析
这里采用尾插法构建新链表。遍历原链表,将不等于 val 的节点依次链接到新链表中。这种方法逻辑直观,但会占用额外的空间。实际工程中若需原地修改,可考虑引入虚拟头节点(Dummy Head)技巧来简化边界处理。
1.3 代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode* newhead = NULL;
ListNode* newtail = NULL;
ListNode* pcur = head;
while (pcur) {
if (pcur->val != val) {
if (newhead == NULL) {
newhead = newtail = pcur;
} else {
newtail->next = pcur;
newtail = pcur;
}
}
pcur = pcur->next;
}
if (newtail) {
newtail->next = NULL;
}
return newhead;
}
二、反转链表
2.1 题目描述
给定单链表的头节点 head,请反转链表并返回新的头节点。
2.2 思路解析
使用三指针迭代法是最常见的解法。定义三个指针:n1 指向前驱节点,n2 指向当前节点,n3 指向后继节点。在遍历过程中,不断调整 n2->next 指向 n1,然后同步移动三个指针。注意处理空链表及链表长度为 1 的特殊情况。
2.3 代码实现
ListNode* {
(head == || head->next == ) {
head;
}
ListNode* n1 = ;
ListNode* n2 = head;
ListNode* n3 = head->next;
(n2) {
n2->next = n1;
n1 = n2;
n2 = n3;
(n3) {
n3 = n3->next;
}
}
n1;
}


