有什么网站可以做深圳初二的试卷练习,网站建设的时间,wordpress多页面统一头部,网站专题设计模板概述
对于一张单向链表#xff0c;我们总是使用双指针实现一些算法逻辑#xff0c;这旨在用常量级别空间复杂度和线性时间复杂度来解决一些问题。
所谓原地算法#xff0c;是指不使用额外空间的算法。
现在#xff0c;我们利用双指针实现以下四种行为。 //Definition fo…概述
对于一张单向链表我们总是使用双指针实现一些算法逻辑这旨在用常量级别空间复杂度和线性时间复杂度来解决一些问题。
所谓原地算法是指不使用额外空间的算法。
现在我们利用双指针实现以下四种行为。
//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 请你反转链表并返回反转后的链表头。
示例 想实现原地翻转那就改变链表的相对位置关系。
我们来想想怎么做
定义双指针prehead和curhead-nextpre总是指向cur的前一个节点。 我们要做的其实就只是把cur转接到head之前即可。
这要分为四步
①断开cur与下一个节点的链接用pre来保存cur之后的节点pre-nextcur-next; ②把cur翻到head之前cur-nexthead; ③现在cur指向的才是headheadcur; ④让cur继续翻转下一个节点curpre-next;
pre已经在这个过程中隐式地向前移动了 这个过程一直程序到cur是nullptr为止。
复杂度 时间复杂度O(n) 空间复杂度O(1) Code
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head||!head-next)return head;ListNode* prehead;ListNode* curhead-next;while(cur){pre-nextcur-next;cur-nexthead;headcur;curpre-next;}return head;}
};
2.原地删除
有一个单链表的 head我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。 要直接删除给定的节点就是给你哪个我就删哪个。
但是单向链表没有前一个节点该怎么删
很简单把给定节点伪装成给定节点下一个节点然后把下一个节点直接干掉。
直接看Code。
复杂度 时间复杂度O(1) 空间复杂度O(1) Code
class Solution {
public:void deleteNode(ListNode* node) {node-valnode-next-val;node-nextnode-next-next;}
};
3.原地取中
给你一个链表的头节点 head 。删除 链表的 中间节点 并返回修改后的链表的头节点 head 。
示例 删除图1的7和图2的3。 用快慢指针快速找到中间位置。
快指针一次两步慢指针一次一步快指针走完是慢指针恰好走到要删除的红色节点处。
证明链表长度为N快指针走到末尾的时间为T。
Vfast2VslowTN/Vfast则XslowT*VslowN/2。
ListNode* slowhead,*fasthead,*prenullptr。
维护slow的前一个节点然后用上一节的原地删除即可。
复杂度 时间复杂度O(n) 空间复杂度O(1) Code
class Solution {
public:ListNode* deleteMiddle(ListNode* head) {if(!head-next)return nullptr;ListNode* slowhead,*fasthead,*prenullptr;while(fastfast-next){preslow;slowslow-next;fastfast-next-next;}pre-nextslow-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]指向了相同的节点。
*注意*链表序并不是原数组序。
这一部分需要讲解
我们先认为i0的位置是头节点也就是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 142C
Code
class Solution {
public:int findDuplicate(vectorint nums) {int fast0,slow0;do{ slownums[slow];fastnums[nums[fast]];}while(slow!fast);fast0;while(slow!fast){slownums[slow];fastnums[fast];}return slow;}
};
总结
原地算法对空间只有几乎可以忽略不计的要求这使得在有空间限制条件时原地算法有着广泛的应用。
我们介绍的这四种链表原地算法兼具了良好的空间复杂度和时间复杂度希望可以启发大家对链表算法的思考。
