当前位置：首页 > news >正文

「链表」链表原地算法合集：原地翻转|原地删除|原地取中|原地查重 / LeetCode 206|237|2095|287（C++）

news 2025/8/2 8:58:48

概述

对于一张单向链表，我们总是使用双指针实现一些算法逻辑，这旨在用常量级别空间复杂度和线性时间复杂度来解决一些问题。

所谓原地算法，是指不使用额外空间的算法。

现在，我们利用双指针实现以下四种行为。

//Definition for singly-linked list.struct ListNode {int val;ListNode *next;ListNode(int x = 0) : val(x), next(NULL) {}ListNode(int x, ListNode* node) : val(x), next(node) {}};

*注意* ：以下算法都暂不考虑动态内存释放问题。

1.原地翻转

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表头。

示例：

想实现原地翻转，那就改变链表的相对位置关系。

我们来想想怎么做：

定义双指针pre=head和cur=head->next，pre总是指向cur的前一个节点。

我们要做的其实就只是把cur转接到head之前即可。

这要分为四步：

①断开cur与下一个节点的链接，用pre来保存cur之后的节点：pre->next=cur->next;

②把cur翻到head之前：cur->next=head;

③现在cur指向的才是head：head=cur;

④让cur继续翻转下一个节点：cur=pre->next;

（pre已经在这个过程中隐式地向前移动了）

这个过程一直程序到cur是nullptr为止。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

Code

class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head||!head->next)return head;ListNode* pre=head;ListNode* cur=head->next;while(cur){pre->next=cur->next;cur->next=head;head=cur;cur=pre->next;}return head;}
};

2.原地删除

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。

要直接删除给定的节点，就是给你哪个，我就删哪个。

但是单向链表没有前一个节点该怎么删？

很简单：把给定节点伪装成给定节点下一个节点，然后把下一个节点直接干掉。

直接看Code。

复杂度

时间复杂度：O(1)

空间复杂度：O(1)

Code

class Solution {
public:void deleteNode(ListNode* node) {node->val=node->next->val;node->next=node->next->next;}
};

3.原地取中

给你一个链表的头节点 head 。删除链表的 中间节点 ，并返回修改后的链表的头节点 head 。

示例：

删除图1的7和图2的3。

用快慢指针快速找到中间位置。

快指针一次两步，慢指针一次一步，快指针走完是慢指针恰好走到要删除的红色节点处。

证明：链表长度为N，快指针走到末尾的时间为T。

Vfast=2Vslow，T=N/Vfast，则Xslow=T*Vslow=N/2。

ListNode* slow=head,*fast=head,*pre=nullptr。

维护slow的前一个节点，然后用上一节的原地删除即可。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

Code

class Solution {
public:ListNode* deleteMiddle(ListNode* head) {if(!head->next)return nullptr;ListNode* slow=head,*fast=head,*pre=nullptr;while(fast&&fast->next){pre=slow;slow=slow->next;fast=fast->next->next;}pre->next=slow->next;return head;}
};

4.原地查重

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

这一节其实并不是链表，但是可由数组映射至链表：

我们将任意数组索引i抽象为链表的节点，nums[i]抽象为链表的next指针。

简单理解：num[]是一个函数，他接受一个链表节点，返回的它的next指针（即数组的索引）

*注意*：我们认为数组下标代表链表节点，即：i是本链表节点，而nums[i]是下一个链表节点。

那么可以认为我们以某种顺序构建了一张环状链表：因为某两个位置的nums[i]指向了相同的节点。

*注意*：链表序并不是原数组序。

这一部分需要讲解：

我们先认为i==0的位置是头节点，也就是1号节点，随后观察：

     i     0 1 2 3 4
nums[i] = [1,3,4,2,2]                       nums[4]=2←---------←↓         ↑                    ↓         ↑
ListNode  0--------->1--------->3--------->2--------→4nums[0]=1  nums[1]=3  nums[3]=2  nums[2]=4

现在我们抽象出了一张假想链表，剩下的判环与找环操作详见上一篇文章：「链表」Floyd判环法（弗洛伊德判圈法|龟兔赛跑法）判环并公式推导找环 / LeetCode 142（C++）

Code

class Solution {
public:int findDuplicate(vector<int>& nums) {int fast=0,slow=0;do{  slow=nums[slow];fast=nums[nums[fast]];}while(slow!=fast);fast=0;while(slow!=fast){slow=nums[slow];fast=nums[fast];}return slow;}
};