文章目录
前言
在学习数据结构的过程中,顺序表和链表是非常重要的基础内容。本篇主要整理顺序表和单链表中比较经典的算法题。
1. 移除元素
题目链接: LeetCode 27. 移除元素
解题思路
这道题可以使用双指针法解决。
定义两个下标:
src:遍历原数组,寻找需要保留的元素。dst:指向新数组中下一个存放元素的位置。
遍历数组,如果当前元素不等于 val,就将其放到 dst 位置,然后 dst++;如果相等,则直接跳过。
遍历结束后,dst 就是删除元素后的数组长度。
例如:
原数组:[3, 2, 2, 3, 4]
val = 3
处理后:[2, 2, 4]
返回:3
代码实现
int removeElement(int* nums, int numsSize, int val)
{
int dst = 0;
for (int src = 0; src < numsSize; src++)
{
if (nums[src] != val)
{
nums[dst] = nums[src]; // 保留当前元素
dst++; // 目标位置后移
}
}
return dst;
}
复杂度分析
- 时间复杂度:O(N),遍历一次数组。
- 空间复杂度:O(1),原地修改数组。
2. 删除有序数组中的重复项
题目链接: LeetCode 26. 删除有序数组中的重复项
解题思路
由于数组已经按照升序排列,相同的元素一定连续出现,因此可以使用双指针法。
定义两个指针:
slow:指向已经保留的最后一个不重复元素。fast:负责向后遍历数组,寻找新的不重复元素。
首先让 slow 指向第一个元素,fast 从第二个元素开始遍历。
如果 nums[fast] 与 nums[slow] 不相等,说明找到了新的元素,将 slow 后移一位,并把新元素放到对应位置。
如果相等,则说明出现了重复元素,直接跳过。
最后返回 slow + 1,即不重复元素的个数。
代码实现
int removeDuplicates(int* nums, int numsSize)
{
if (numsSize == 0)
return 0;
int slow = 0;
for (int fast = 1; fast < numsSize; fast++)
{
if (nums[fast] != nums[slow])
{
slow++;
nums[slow] = nums[fast]; // 保存新的不重复元素
}
}
return slow + 1;
}
复杂度分析
- 时间复杂度:O(N),只遍历一次数组。
- 空间复杂度:O(1),不需要额外空间。
3. 合并两个有序数组
题目链接: LeetCode 88. 合并两个有序数组
解题思路
这道题可以使用三个指针,从后往前进行合并。
定义三个下标:
i:指向nums1最后一个有效元素。j:指向nums2最后一个元素。k:指向nums1最后一个位置。
每次比较 nums1[i] 和 nums2[j],将较大的元素放到 nums1[k],然后移动对应指针。
为什么要从后往前合并?
因为 nums1 后面已经预留了空间,如果从前往后合并,可能会覆盖原来还没有处理的元素。从后往前则不会出现这个问题。
当 nums2 中的元素全部放入后,合并结束。因为 nums1 剩余的元素本来就在正确的位置。
代码实现
void merge(int* nums1, int m, int* nums2, int n)
{
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0)
{
if (i >= 0 && nums1[i] > nums2[j])
{
nums1[k--] = nums1[i--]; // 放入较大的元素
}
else
{
nums1[k--] = nums2[j--];
}
}
}
复杂度分析
- 时间复杂度:O(M+N),两个数组中的元素最多遍历一次。
- 空间复杂度:O(1),直接在原数组中完成合并。
4. 移除链表元素
题目链接: LeetCode 203. 移除链表元素
解题思路
遍历链表,删除所有值等于 val 的结点。
这里使用虚拟头结点(哨兵结点),可以统一处理头结点和普通结点的删除操作。
创建一个虚拟头结点 dummy,让它指向原链表头结点,再使用 cur 指针遍历链表。
- 如果
cur->next的值等于val,就删除该结点。 - 否则让
cur向后移动。
需要注意:删除结点后,cur 不需要移动,因为新的 cur->next 仍然需要判断,避免漏掉连续出现的目标元素。
代码实现
struct ListNode* removeElements(
struct ListNode* head, int val)
{
struct ListNode dummy;
dummy.next = head; // 虚拟头结点指向原链表
struct ListNode* cur = &dummy;
while (cur->next != NULL)
{
if (cur->next->val == val)
{
struct ListNode* del = cur->next;
cur->next = del->next; // 跳过需要删除的结点
free(del); // 释放结点空间
}
else
{
cur = cur->next; // 不需要删除,继续遍历
}
}
return dummy.next; // 返回新的头结点
}
复杂度分析
- 时间复杂度:O(N),遍历一次链表。
- 空间复杂度:O(1),只使用常数个额外变量。
5. 反转链表
题目链接: LeetCode 206. 反转链表
解题思路
反转链表就是改变每个结点 next 指针的指向,使其指向前一个结点。
例如:
原链表:1 -> 2 -> 3 -> NULL
反转后:3 -> 2 -> 1 -> NULL
这里使用三个指针:
prev:记录当前结点的前一个结点。cur:当前正在处理的结点。next:提前保存当前结点的下一个结点。
每次先保存 next,再修改 cur->next,然后依次移动三个指针。
为什么需要 next?
因为修改 cur->next 后,原来的后续结点就可能丢失,所以必须提前保存。
遍历结束后,prev 就是反转后的新头结点。
代码实现
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while (cur != NULL)
{
struct ListNode* next = cur->next; // 保存下一个结点
cur->next = prev; // 反转当前结点的指针
prev = cur; // prev 向后移动
cur = next; // cur 继续处理下一个结点
}
return prev; // 返回反转后的新头结点
}
复杂度分析
- 时间复杂度:O(N),每个结点只处理一次。
- 空间复杂度:O(1),只使用三个指针。
6. 链表的中间结点
题目链接: LeetCode 876. 链表的中间结点
解题思路
这道题可以使用快慢指针法。
定义两个指针:
slow:慢指针,每次移动一步。fast:快指针,每次移动两步。
两个指针都从链表头结点开始。当快指针到达链表末尾时,慢指针刚好位于链表中间。
例如:
1 -> 2 -> 3 -> 4 -> 5 -> 6
↑
中间位置
由于快指针一次走两步,慢指针一次走一步,因此当快指针走完整个链表时,慢指针只走了一半。
另外,如果链表长度为偶数,慢指针最终会指向第二个中间结点,符合题目要求。
代码实现
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
// 快指针必须保证能够向后移动两步
while (fast != NULL && fast->next != NULL)
{
slow = slow->next; // 慢指针走一步
fast = fast->next->next; // 快指针走两步
}
return slow;
}
复杂度分析
- 时间复杂度:O(N),快指针最多遍历链表的一半。
- 空间复杂度:O(1),只使用两个指针。
7. 合并两个有序链表
题目链接: LeetCode 21. 合并两个有序链表
解题思路
两个链表都已经按照升序排列,因此只需要比较当前结点的值,将较小的结点连接到新链表的末尾。
这里使用虚拟头结点 dummy 和尾指针 tail。
具体步骤:
- 创建虚拟头结点,让
tail指向它。 - 比较两个链表当前结点的值。
- 将较小的结点连接到
tail后面。 - 移动对应链表的指针,同时移动
tail。 - 当其中一个链表遍历结束后,将另一个链表剩余部分直接连接。
这里不需要重新创建数据结点,直接调整原链表结点的指针即可。
代码实现
struct ListNode* mergeTwoLists(
struct ListNode* list1,
struct ListNode* list2)
{
struct ListNode dummy;
dummy.next = NULL;
struct ListNode* tail = &dummy;
while (list1 != NULL && list2 != NULL)
{
if (list1->val <= list2->val)
{
tail->next = list1; // 连接较小的结点
list1 = list1->next;
}
else
{
tail->next = list2;
list2 = list2->next;
}
tail = tail->next; // 尾指针向后移动
}
// 将剩余链表直接连接到尾部
tail->next = (list1 != NULL) ? list1 : list2;
return dummy.next;
}
复杂度分析
- 时间复杂度:O(M+N),每个结点最多访问一次。
- 空间复杂度:O(1),不需要额外创建数据结点。
8. 链表分割
题目链接: 牛客网:链表分割
解题思路
这道题要求将链表分成两个部分:
- 第一部分存放所有小于
x的结点。 - 第二部分存放所有大于或等于
x的结点。
同时还需要保证每一部分内部原来的相对顺序不变。
可以使用两个链表分别存放这两类结点,再将它们连接起来。
具体做法:
- 创建两个虚拟头结点,分别表示两条链表。
- 使用两个尾指针,负责将结点插入对应链表的末尾。
- 遍历原链表,根据结点值决定插入哪条链表。
- 最后将两条链表连接起来。
这里使用尾插法,可以保留结点原来的相对顺序。
代码实现
struct ListNode* partition(
struct ListNode* pHead, int x)
{
struct ListNode lessDummy;
struct ListNode greaterDummy;
lessDummy.next = NULL;
greaterDummy.next = NULL;
struct ListNode* lessTail = &lessDummy;
struct ListNode* greaterTail = &greaterDummy;
struct ListNode* cur = pHead;
while (cur != NULL)
{
struct ListNode* next = cur->next; // 保存下一个结点
cur->next = NULL; // 断开当前结点
if (cur->val < x)
{
lessTail->next = cur; // 尾插到小于x的链表
lessTail = cur;
}
else
{
greaterTail->next = cur; // 尾插到另一条链表
greaterTail = cur;
}
cur = next;
}
// 将两条链表连接起来
lessTail->next = greaterDummy.next;
return lessDummy.next;
}
复杂度分析
- 时间复杂度:O(N),只遍历一次原链表。
- 空间复杂度:O(1),只使用常数个额外指针。
9. 链表的回文结构
题目链接: 牛客网:链表的回文结构
解题思路
回文结构要求链表从前往后和从后往前读取的结果相同。
例如:
1 -> 2 -> 3 -> 2 -> 1
可以结合快慢指针和链表反转来解决。
具体步骤:
- 使用快慢指针找到链表的中间位置。
- 如果链表长度为奇数,跳过中间结点。
- 将后半部分链表反转。
- 分别遍历前半部分和反转后的后半部分,比较结点值。
- 如果所有对应结点都相同,则说明是回文结构。
例如:
原链表:1 -> 2 -> 3 -> 2 -> 1
反转后半部分:
前半部分:1 -> 2
后半部分:1 -> 2
两部分对应结点的值相同,因此是回文结构。
比较完成后,还可以再次反转后半部分,将原链表恢复。
代码实现
// 反转链表
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while (cur != NULL)
{
struct ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
bool chkPalindrome(struct ListNode* A)
{
if (A == NULL || A->next == NULL)
return true;
struct ListNode* slow = A;
struct ListNode* fast = A;
// 第一步:寻找链表中间位置
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
// 奇数个结点,跳过中间结点
if (fast != NULL)
slow = slow->next;
// 第二步:反转后半部分
struct ListNode* second = reverseList(slow);
struct ListNode* p1 = A;
struct ListNode* p2 = second;
bool ret = true;
// 第三步:比较前后两部分
while (p2 != NULL)
{
if (p1->val != p2->val)
{
ret = false;
break;
}
p1 = p1->next;
p2 = p2->next;
}
// 第四步:恢复原链表
reverseList(second);
return ret;
}
复杂度分析
- 时间复杂度:O(N),寻找中间结点、反转和比较都需要线性时间。
- 空间复杂度:O(1),不需要额外数组或栈。
10. 相交链表
题目链接: LeetCode 160. 相交链表
解题思路
两个链表相交,指的是它们从某个结点开始共享后面的结点,而不是两个结点的数值相同。
这道题可以使用双指针法。
定义两个指针:
pA:从链表 A 的头结点开始。pB:从链表 B 的头结点开始。
两个指针同时向后移动。当一个指针遍历完自己的链表后,就转到另一个链表的头部继续遍历。
为什么这样可以找到相交结点?
假设链表 A 的长度为 a,链表 B 的长度为 b,相交部分长度为 c。
那么两个指针最终走过的距离都是:
a + b - c
因此,如果两个链表相交,两个指针最终会在相交结点相遇;如果不相交,则最终都会到达 NULL。
代码实现
struct ListNode* getIntersectionNode(
struct ListNode* headA,
struct ListNode* headB)
{
struct ListNode* pA = headA;
struct ListNode* pB = headB;
while (pA != pB)
{
// A链表遍历结束后,转到B链表
pA = (pA == NULL) ? headB : pA->next;
// B链表遍历结束后,转到A链表
pB = (pB == NULL) ? headA : pB->next;
}
return pA; // 相交返回交点,不相交返回NULL
}
复杂度分析
- 时间复杂度:O(M+N),最多遍历两个链表各一次。
- 空间复杂度:O(1),只使用两个指针。
11. 环形链表 I
题目链接: LeetCode 141. 环形链表
解题思路
这道题需要判断链表中是否存在环,可以使用快慢指针法。
定义两个指针:
slow:每次走一步。fast:每次走两步。
两个指针从链表头结点同时出发。
如果链表不存在环,快指针最终会走到 NULL。
如果链表存在环,快指针进入环后会不断追赶慢指针。
由于快指针每次比慢指针多走一步,因此两个指针之间的距离会不断缩小,最终一定会相遇。
所以,只需要判断两个指针是否相遇即可。
代码实现
bool hasCycle(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next; // 慢指针走一步
fast = fast->next->next; // 快指针走两步
if (slow == fast)
return true; // 相遇说明存在环
}
return false; // 快指针到达链表末尾,不存在环
}
复杂度分析
- 时间复杂度:O(N),快慢指针最多遍历线性数量的结点。
- 空间复杂度:O(1),只使用两个指针。
12. 环形链表 II
题目链接: LeetCode 142. 环形链表 II
解题思路
这道题是在环形链表 I 的基础上,进一步寻找环的入口。
同样使用快慢指针,分为两个阶段。
第一阶段:寻找相遇点。
慢指针每次走一步,快指针每次走两步。如果两者相遇,说明链表存在环。
第二阶段:寻找环的入口。
快慢指针相遇后:
- 将一个新指针
p放到链表头结点。 - 保留慢指针在相遇点。
- 两个指针每次都走一步。
- 两个指针再次相遇的位置就是环的入口。
原理推导:
假设:
L:链表头结点到环入口的距离。X:环入口到第一次相遇点的距离。C:环的周长。
快慢指针第一次相遇时,慢指针走过的距离为:
L + X
快指针走过的距离为:
L + X + nC
其中 n 表示快指针比慢指针多绕过的环的圈数。
由于快指针的速度是慢指针的两倍:
2(L + X) = L + X + nC
整理得到:
L + X = nC
L = nC - X
这说明,从链表头结点出发走 L 步,与从相遇点出发走 L 步,最终都会到达环的入口。
因此,让两个指针分别从头结点和相遇点出发,每次走一步,最终就会在环入口相遇。
代码实现
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
// 第一阶段:寻找快慢指针的相遇点
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
// 第二阶段:寻找环的入口
struct ListNode* p = head;
while (p != slow)
{
p = p->next; // 从头结点出发
slow = slow->next; // 从相遇点出发
}
return p; // 返回环的入口
}
}
return NULL; // 不存在环
}
复杂度分析
- 时间复杂度:O(N),寻找相遇点和环入口都只需要线性时间。
- 空间复杂度:O(1),只使用常数个指针。
13. 随机链表的复制
题目链接: LeetCode 138. 随机链表的复制
解题思路
这道题的链表结点除了 next 指针,还有一个 random 指针,可以指向任意结点或者 NULL。
要求复制整个链表,新链表中的结点必须是独立创建的,不能直接使用原链表的结点。
这里使用一种比较巧妙的方法:将复制结点插入原结点后面。
整个过程分为三个步骤。
第一步:复制结点。
遍历原链表,为每个结点创建一个新结点,并将它插入原结点后面。
例如:
原链表:A -> B -> C
插入后:A -> A' -> B -> B' -> C -> C'
这样,每个原结点的下一个结点就是它对应的复制结点。
第二步:复制 random 指针。
假设原结点 A 的 random 指向 C,那么复制结点 A’ 的 random 就应该指向 C’。
由于 C’ 就在 C 的后面,因此可以直接使用:
A->next->random = A->random->next;
这样就能找到对应的复制结点。
第三步:拆分链表。
将原链表和复制链表分离,恢复两个独立的链表。
最终得到:
原链表:A -> B -> C
复制链表:A' -> B' -> C'
代码实现
struct Node* copyRandomList(struct Node* head)
{
if (head == NULL)
return NULL;
struct Node* cur = head;
// 第一步:复制结点,插入原结点后面
while (cur != NULL)
{
struct Node* copy =
(struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
copy->random = NULL;
copy->next = cur->next;
cur->next = copy;
cur = copy->next;
}
// 第二步:复制random指针
cur = head;
while (cur != NULL)
{
struct Node* copy = cur->next;
if (cur->random != NULL)
{
// 原结点random指向的结点,其next就是对应的复制结点
copy->random = cur->random->next;
}
cur = copy->next;
}
// 第三步:拆分原链表和复制链表
cur = head;
struct Node* copyHead = head->next;
while (cur != NULL)
{
struct Node* copy = cur->next;
cur->next = copy->next; // 恢复原链表
if (copy->next != NULL)
{
copy->next = copy->next->next; // 连接下一个复制结点
}
cur = cur->next;
}
return copyHead;
}
复杂度分析
- 时间复杂度:O(N),需要遍历链表三次。
- 空间复杂度:O(1),不计算新复制的结点所占空间。
算法思想总结
通过以上题目的学习,可以发现,很多算法题虽然题目不同,但使用的核心思想往往是相通的。以下是本篇涉及的几种常见算法思想。
- 双指针法
双指针法通过设置两个指针,按照不同的规则移动,减少不必要的遍历,提高算法效率。
典型题目:
- 移除元素
- 删除有序数组中的重复项
- 合并两个有序数组
- 相交链表
- 快慢指针法
快慢指针通常用于链表问题,通过控制两个指针不同的移动速度来解决问题。
典型题目:
- 链表的中间结点
- 链表的回文结构
- 环形链表 I
- 环形链表 II
- 虚拟头结点
虚拟头结点是链表操作中非常实用的技巧。通过创建一个不存储有效数据的头结点,可以统一处理头结点和普通结点的插入、删除等操作,减少特殊情况的判断。
典型题目:
- 移除链表元素
- 合并两个有序链表
- 链表分割
- 链表反转
链表反转的核心是修改结点之间的指针指向,通常使用三个指针完成操作。掌握这一方法,也有助于解决一些需要反向比较或重新组织链表的问题。
典型题目:
- 反转链表
- 链表的回文结构
转载自 CSDN-专业IT技术社区
原文链接:https://blog.csdn.net/2601_96015117/article/details/170605137




