跳到主要内容数据结构：顺序表与链表经典算法实战 | 极客日志C++算法
数据结构：顺序表与链表经典算法实战
本文涵盖顺序表与链表的核心算法实战。包括移除元素、去重、合并有序数组的双指针技巧；链表反转、中间节点查找、回文检测及相交判断的快慢指针应用；以及环形链表的判定与入口定位。重点解析哨兵节点优化、空间复杂度控制及边界条件处理，提供可直接运行的 C++ 参考实现。
Kubernet0 浏览 数据结构：顺序表与链表经典算法实战
在数据结构的学习中，顺序表和链表是最基础也最重要的两种线性结构。掌握它们的常见操作算法，不仅是面试的必考题，更是理解后续复杂数据结构的基石。本文将通过 LeetCode 和牛客网的经典例题，深入剖析双指针、快慢指针等核心技巧。
顺序表算法题（双指针法）
1. 移除元素
题目链接： 移除元素
思路解析：
这道题的核心在于原地修改数组。我们可以使用双指针法：一个指针 src 负责向前探路，寻找不等于目标值 val 的元素；另一个指针 dst 负责在后面站岗，记录有效数据的写入位置。
当 src 指向的数据不是 val 时，将其赋值给 dst 指向的位置，然后两个指针同时后移；如果是 val，则只移动 src。最终 dst 的值即为新数组的长度。
int removeElement(int* nums, int numsSize, int val) {
int src = 0, dst = 0;
while (src < numsSize) {
if (nums[src] != val) {
nums[dst++] = nums[src];
}
src++;
}
return dst;
}
2. 删除有序数组中的重复项
题目链接： 删除有序数组中的重复项
思路解析：
同样是双指针，但逻辑略有不同。由于数组已排序，相同的元素会相邻。我们让 src 从索引 1 开始， 从 0 开始。
dst
如果 nums[src] 与 nums[dst] 不相等，说明遇到了新元素，dst 前进一步并复制该值；如果相等，则跳过。注意优化点：只有当 dst 移动后才赋值，避免自己给自己赋值的冗余操作。
int removeDuplicates(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int src = 1, dst = 0;
while (src < numsSize) {
if (nums[src] != nums[dst]) {
dst++;
nums[dst] = nums[src];
}
src++;
}
return dst + 1;
}
3. 合并两个有序数组
思路解析：
通常合并数组是从前往后比，但这里 nums1 有足够空间存放结果。为了避免覆盖未处理的元素，我们从后往前遍历。比较两个数组末尾的元素，将较大的放入 nums1 的末尾。
这样既利用了现有空间，又避免了额外的内存开销。只需处理其中一个数组越界的情况即可。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;
while (l1 >= 0 && l2 >= 0) {
if (nums1[l1] > nums2[l2]) {
nums1[l3--] = nums1[l1--];
} else {
nums1[l3--] = nums2[l2--];
}
}
while (l2 >= 0) {
nums1[l3--] = nums2[l2--];
}
}
链表算法题（快慢指针，三指针法）
4. 移除链表元素
思路解析：
这里所谓的'创建新链表'其实是指构建一个新的逻辑结构，本质上还是通过修改原链表的指针来实现。我们需要遍历原链表，将不等于 val 的节点尾插到新链表中。
关键点在于处理头结点可能为空或需要被移除的情况，以及最后务必将尾节点的 next 置为 NULL，防止形成环。
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode* newHead = NULL, *newTail = NULL;
ListNode* pcur = head;
while (pcur) {
if (pcur->val != val) {
if (!newHead) {
newHead = newTail = pcur;
} else {
newTail->next = pcur;
newTail = pcur;
}
}
pcur = pcur->next;
}
if (newTail) newTail->next = NULL;
return newHead;
}
5. 反转链表
- 头插法： 遍历原链表，将每个节点插入到新链表的头部。注意保存下一个节点，并将旧头结点的
next 置空以防成环。
- 三指针法： 使用
prev, curr, next 三个指针，逐个改变指针指向。这种方法更直观，适合理解指针变换过程。
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
ListNode* pcur = head;
ListNode* newHead = NULL;
while (pcur) {
ListNode* next = pcur->next;
pcur->next = newHead;
newHead = pcur;
pcur = next;
}
return newHead;
}
typedef struct ListNode ListNode;
struct ListNode* reverseList_v2(struct ListNode* head) {
if (!head) return NULL;
ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;
while (n2) {
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3) n3 = n3->next;
}
return n1;
}
6. 链表的中间节点
思路解析：
经典的快慢指针应用。定义 slow 每次走一步，fast 每次走两步。当 fast 到达末尾时，slow 正好位于中间。
注意循环条件 fast != NULL && fast->next != NULL，利用短路求值保护空指针访问。
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
7. 合并两个有序链表
思路解析：
同样采用尾插法构建新链表。比较两个链表当前节点的值，将较小的节点接在新链表尾部。
为了简化代码逻辑，可以使用哨兵位（Sentinel Node）。创建一个虚拟头结点，最后返回其 next 即可。这样就不需要单独判断头结点是否为空的情况，代码会更简洁。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail = dummy;
ListNode* l1 = list1, *l2 = list2;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
ListNode* ret = dummy->next;
free(dummy);
return ret;
}
8. 链表分割
思路解析：
题目要求将小于 x 的节点放在前面，大于等于 x 的放在后面。我们可以维护两条链表：一条存小值，一条存大值。遍历原链表，分别尾插到这两条链表中。最后将小链表的尾部连接到大链表的头部。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* lessTail = lessHead;
ListNode* greatHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* greatTail = greatHead;
ListNode* pcur = pHead;
while (pcur) {
if (pcur->val < x) {
lessTail->next = pcur;
lessTail = lessTail->next;
} else {
greatTail->next = pcur;
greatTail = greatTail->next;
}
pcur = pcur->next;
}
greatTail->next = NULL;
lessTail->next = greatHead->next;
ListNode* ret = lessHead->next;
free(lessHead);
free(greatHead);
return ret;
}
};
9. 链表的回文结构
- 数组法： 遍历链表存入数组，然后用双指针检查数组是否对称。空间复杂度 O(N)。
- 反转法： 找到中间节点，将后半部分链表反转，然后与前半部分逐一比较。空间复杂度 O(1)。这是更优解。
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head) {
if (!head) return NULL;
ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;
while (n2) {
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3) n3 = n3->next;
}
return n1;
}
bool chkPalindrome(ListNode* A) {
ListNode* mid = middleNode(A);
ListNode* right = reverseList(mid);
ListNode* left = A;
while (right) {
if (left->val != right->val) return false;
left = left->next;
right = right->next;
}
return true;
}
};
10. 相交链表
思路解析：
如果两个链表相交，它们从交点开始后面的节点是共享的，因此尾节点必然相同。我们可以通过计算两个链表的长度差，让长链表先走几步，使两个指针处于同一起跑线，然后同步遍历直到相遇。
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
ListNode* pa = headA, *pb = headB;
int sizeA = 0, sizeB = 0;
while (pa) { ++sizeA; pa = pa->next; }
while (pb) { ++sizeB; pb = pb->next; }
int gap = abs(sizeA - sizeB);
ListNode* shortList = sizeA > sizeB ? headB : headA;
ListNode* longList = sizeA > sizeB ? headA : headB;
while (gap--) longList = longList->next;
while (shortList) {
if (shortList == longList) return shortList;
shortList = shortList->next;
longList = longList->next;
}
return NULL;
}
环形链表（快慢指针进阶）
1. 环形链表 I
思路解析：
依然使用快慢指针。slow 走一步，fast 走两步。如果链表有环，fast 最终一定会追上 slow。如果 fast 遇到 NULL，则无环。
关于为什么快指针走三步不行？理论上如果环长和步数满足特定数学关系（如环长为偶数且步数为奇数），可能会错过。但在常规的双指针设定下，快慢指针速度比为 2:1 是最稳妥的相遇策略。
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
2. 环形链表 II
思路解析：
在检测到环后，如何找到入环口？
设头结点到入环口的距离为 L，入环口到相遇点的距离为 X，环长为 R。
根据快慢指针路程关系：2(L+X) = L+X+nR，推导出 L = (n-1)R + (R-X)。
这意味着：从头结点走 L 步的距离，等于从相遇点走 (R-X) 步的距离。因此，当一个指针从头出发，另一个从相遇点出发，两者速度均为 1，再次相遇的点即为入环口。
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* pcur = head;
while (pcur != slow) {
pcur = pcur->next;
slow = slow->next;
}
return pcur;
}
}
return NULL;
}
以上涵盖了顺序表和链表最核心的算法场景。在实际开发中，这些技巧往往能帮助我们优化性能，减少不必要的内存分配。建议读者结合具体题目多动手实现，加深理解。
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
