C++算法
LeetCode 链表经典题目解析：移除、反转、中间节点与回文结构
本文详细解析了 LeetCode 中五个经典的链表算法题目。内容包括移除链表元素的双指针法、合并两个有序链表的哨兵位优化、反转链表的头插与三指针法、查找中间节点的快慢指针技巧，以及判断链表回文结构的两种方案。文章提供 C/C++ 代码实现及思路图解，旨在帮助开发者巩固数据结构基础，提升算法解题能力。
本文详细解析了 LeetCode 中五个经典的链表算法题目。内容包括移除链表元素的双指针法、合并两个有序链表的哨兵位优化、反转链表的头插与三指针法、查找中间节点的快慢指针技巧，以及判断链表回文结构的两种方案。文章提供 C/C++ 代码实现及思路图解，旨在帮助开发者巩固数据结构基础，提升算法解题能力。
题目链接：移除链表元素
根据题目描述，我们需要将链表中值为 val 的节点删除，并返回新链表的头结点。
使用之前实现的 Find 方法找到对应值，然后使用 Erase 方法删除，直到 Find 返回空指针。此方法实现简单，但效率较低。
使用双指针法。新建一个链表，遍历原链表，如果当前节点值不等于 val，则尾插到新链表。注意处理新链表头为空的情况，并在最后将新链表尾结点的 next 置为 NULL。
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode* newhead = NULL, *newtail = NULL;
newhead = 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;
}
题目链接：合并两个有序链表
题目要求将两个有序链表合并成一个新的有序链表。
使用双指针遍历两个链表，比较节点大小，将较小的节点尾插到新链表。当一个链表遍历完后，将另一个链表剩余部分直接接在新链表后。需特殊处理空链表情况。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (list1 == NULL) return list2;
if (list2 == NULL) return list1;
struct ListNode* pcur1 = list1, *pcur2 = list2;
struct ListNode* newhead = NULL, *newtail = NULL;
while (pcur1 && pcur2) {
if (pcur1->val < pcur2->val) {
if (newhead == NULL) {
newhead = newtail = pcur1;
} else {
newtail->next = pcur1;
newtail = pcur1;
}
pcur1 = pcur1->next;
} else {
if (newhead == NULL) {
newhead = newtail = pcur2;
} else {
newtail->next = pcur2;
newtail = pcur2;
}
pcur2 = pcur2->next;
}
}
if (pcur1) newtail->next = pcur1;
if (pcur2) newtail->next = pcur2;
return newhead;
}
上述代码每次插入前都需判断链表是否为空。可以使用哨兵位（Sentinel Node）简化逻辑。申请一个不保存数据的头结点作为哨兵，直接在其后尾插，最后返回哨兵的下一个节点，记得释放哨兵位内存。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* pcur1 = list1, *pcur2 = list2;
struct ListNode* guard = NULL, *tail = NULL;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;
while (pcur1 && pcur2) {
if (pcur1->val < pcur2->val) {
tail->next = pcur1;
tail = tail->next;
pcur1 = pcur1->next;
} else {
tail->next = pcur2;
tail = tail->next;
pcur2 = pcur2->next;
}
}
if (pcur1) tail->next = pcur1;
if (pcur2) tail->next = pcur2;
struct ListNode* head = guard->next;
free(guard);
return head;
}
题目链接：反转链表
题目要求改变指针指向，使链表反转。
创建新链表，遍历原链表，使用头插法将节点插入新链表。
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* cur = head, *newhead = NULL;
while (cur) {
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
修改原链表节点的指针指向，使用三个指针（prev, curr, next）依次反转，空间复杂度 O(1)。
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL) return head;
struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;
while (n2) {
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3) n3 = n3->next;
}
return n1;
}
题目链接：链表的中间节点
返回链表的中间节点，若节点数为偶数，返回后一个中间节点。
先遍历统计节点总数 count，再遍历 count/2 次找到中间节点。
struct ListNode* middleNode(struct ListNode* head) {
int count = 0;
struct ListNode* pcur = head;
while (pcur) {
count++;
pcur = pcur->next;
}
count /= 2;
pcur = head;
while (count--) {
pcur = pcur->next;
}
return pcur;
}
使用快慢指针。快指针一次走两步，慢指针一次走一步。当快指针到达末尾时，慢指针即指向中间节点。
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* fast, *slow;
fast = slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
题目链接：链表的回文结构
判断链表是否前后对称。C++ 中可使用类封装。
将链表数据存入数组，使用左右双指针比较数组元素是否对称。虽然题目要求空间复杂度 O(1)，但给定节点数上限，定长数组可视为常数空间。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
int arr[901] = {0};
ListNode* pcur = A;
int i = 0;
while (pcur) {
arr[i++] = pcur->val;
pcur = pcur->next;
}
int left = 0, right = i - 1;
while (left < right) {
if (arr[left] != arr[right]) return false;
left++, right--;
}
return true;
}
};
利用之前的函数，先找中间节点，反转后半部分链表，然后与原前半部分比较。
class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* cur = head, *newhead = NULL;
while (cur) {
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* fast, *slow;
fast = slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool chkPalindrome(ListNode* head) {
struct ListNode* mid = middleNode(head);
struct ListNode* rhead = reverseList(mid);
while (head && rhead) {
if (head->val != rhead->val) return false;
head = head->next;
rhead = rhead->next;
}
return true;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online