大佬教程收集整理的这篇文章主要介绍了数据结构之超硬核热门复杂度、数组、链表OJ题2W+文字+图片详解，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
首先我们先了解一下OJ题的形式c;形式有两种：
提供一个接口函数c;而不是完整程序c;实现这个函数就可以了c;提交程序以后c;这段代码被提交到OJ服务器上c;它还要和其他测试程序(头文件、main函数)进行合并
测试用例一般是通过参数和返回值进行交互的。
写代码区域什么都不给你c;自己写完整的程序c;头文件c;主函数c;算法逻辑
我们要去接口IO输入测试用例c;要把结构按格式输出
题目描述：
数组nums包含从0到n的所有整数c;但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：
输入：[3,0,1] 输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1] 输出：8
题目来源：消失的数字
解法1:
首先排序c;然后依次查找上一个数+1是否等于下一个数c;等于就继续c;不等于这个数就是缺失的数字
但是复杂度不符合要求c;qsort快排c;时间复杂度O(N*logN)c;而题目要求是O(n)c;故我们看下一种解法：
解法2：
代码如下：
int @H_572_184@missingnumber(int* nums,int numssize)
{
int i=0;
int sum=0;
int sum1=0;
for(i=0;i<numssize;i++)
{
sum+=nums[i];
}
for(i=1;i<=numssize;i++)
{
sum1+=i;
}
return sum1-sum;
}
解法3：
看解法3的思路之前我们需要知道一个知识：两个相同的数异或等于0c;0和任何数异或等于它本身
比如3异或3c;不同为1c;他们的二进制位都是相同的c;故全是0c;所以等于0
解法3思路：
创建一个变量x=0c;x先跟数组中值异或c;再跟与0-n之间的数异或c;相当于其他数出现了两次c;出现两次的都异或都成为了0c;缺失的数字只出现一次c;故最好x就是缺失的数字
时间复杂度O(N)c;满足要求
代码如下：
int @H_572_184@missingnumber(int* nums,int numssize)
{
int x=0;
//先跟数组中值异或
for(int i=0;i<numssize;i++)
{
x^=nums[i];
}
//再跟0-n的数字异或
for(int i=0;i<=numssize;i++)
{
x^=i;
}
return x;
}
题目描述：
给定一个数组c;将数组中的元素向右移动 k 个位置c;其中 k 是非负数。
进阶：
尽可能想出更多的解决方案c;至少有三种不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]
题目来源：旋转数组
解法一：
右旋一次：保留最后一个值到temp变量c;数组中值都向右移动一次c;再把temp放到最左边
然后外面套一层循环c;右旋k次
时间复杂度：0(N*(K%N))->最好是K==N时c;时间复杂度位O(1) c;最坏是O(N^2) c;是在K==N-1时c;时间复杂度考虑最坏情况c;故时间复杂度为O(N^2)c;这个方法的时间性能不高
空间复杂度为O(1)
代码如下：
void rotate(char*str,int k)
{
int i=0;
int len=strlen(str)
for(i=0;i<k%len;i++)
{
char temp=str[len-1]
int j=0;
for(j=len-1;j>0;j--)
{
str[j]=str[j-1];
}
str[0]=temp;
}
}
解法二：
思路：
代码如下：
int @H_572_184@main()
{
int arr1[] = { 1,2,3,4,5,6,7 };
int arr2[10] = { 0 };
int k = 0;
scanf("%d", &k);
int sz = sizeof(arr1) / sizeof(arr1[0]);
int i = 0;
//把后k个数放在第二个数组的前k个上
for (i = 0; i < k; i++)
{
arr2[i] = arr1[sz - k + i];
}
//把前n-k个数放在第二个数组的后面
for (i = 0; i < sz - k; i++)
{
arr2[k + i] = arr1[i];
}
for (i = 0; i < sz; i++)
{
printf("%d ", arr2[i]);
}
return 0;
}
时间复杂度：O(N)
空间复杂度：O(N)
这样可以解决这个问题c;但是这个OJ题是不能这样写的c;因为这个OJ题是接口型的：
@H_103_944@
我们将数组一的元素放在数组二c;我们没有改变数组一的旋转c;只是将数组一旋转的结果放在了数组二c;况且这个函数的返回值为voidc;我们也不能将数组二返回c;所有这个思路我们有这个想法就好了c;这是解决的一种方法c;但是不能过而已。
下面看解法3c;这个是最优的解法
解法3：三步翻转法
1、将前n-k个数逆置
2、后k个数逆置
3、整体逆置
void reverse(int *nums,int begin,int end)
{
while(begin<end)
{
int temp=nums[begin];
nums[begin]=nums[end];
nums[end]=temp;
begin++;
end--;
}
}
void rotate(int *nums,int numssize,int k)
{
k%=numssize;
reverse(nums,0,numssize-k-1);
//将前n-k个数逆置
reverse(nums,numssize-k,numssize-1);
//后k个数逆置
reverse(nums,0,numssize-1);
//整体逆置
}
这个解法的时间复杂度：O(N)c;空间复杂度：O(1)c;都是最优的c;建议大家写第三个解法c;代码也不难c;只需写一个逆置的函数c;只需要注意逆置传参时对于前n-k个和后k个的参数的把握要明确。
下面我们来看顺序表数组中的一些OJ题：
题目描述：
给你一个数组 nums 和一个值 valc;你需要 原地 移除所有数值等于 val 的元素c;并返回移除后数组的新长度。
题目来源：移除元素
原地移除数组中所有的元素valc;要求时间复杂度为O(N)c;空间复杂度为O(1)
思路1：
时间复杂度：O(N^2)
空间复杂度：O(1)
int removeElement(int* nums, int numsSize, int val)
{
int i = 0;
int temp = numsSize;
//1234546
for (i = 0; i < numsSize; i++)
{
if (nums[i] == val)
{
int begin = i;
while (begin<numsSize-1)
{
nums[begin] = nums[begin + 1];
begin++;
}
temp--;//数组当前元素个数
i--;
numsSize--;
}
}
return temp;
}
//测试代码
int @H_572_184@main()
{
int nums[]={1,2,3,4,5,4,6};
int numsSize=sizeof(nums)/sizeof(nums[0]);
int ret = removeElement(nums,numsSize,4);
for(int i=0;i<ret;i++)
{
printf("%d ",nums[i]);
}
return 0;
}
在每次挪动数据后我们需要将i–c;因为此时下标的i值为val的下标c;val后面的元素前移了c;此时的i下标对应的是val的下一个元素c;故应该让i保持不变继续遍历c;同时遍历的次数也应该少c;防止越界c;我们也要让numsSize–c;temp来记录元素个数。
思路2：
空间换时间：把原数组中不是3的所有值c;拷贝到新数组c;再拷贝回来c;时间复杂度O(N)c;空间复杂度O(N)c;只不过这里不满足题的要求c;因为题目空间复杂度要求O(N)
我们这里能知道这个思路就可以了c;这个思路是不能解这道题的c;因为题目空间复杂度要求O(N)c;思路2测试代码如下：
int removeElement(int* nums1, int* nums2, int numsSize, int val)
{
int i = 0;
int temp = 0;
for (i = 0; i < numsSize; i++)
{
if (nums1[i] != val)
{
nums2[i] = nums1[i];
temp++;
}
else
{
nums2--;
}
}
return temp;
}
int @H_572_184@main()
{
int nums1[] = { 1,2,3,4,5,4,6 };
int nums2[8] = {0};//1,2,3,5,6
int numsSize = sizeof(nums1) / sizeof(nums1[0]);
int ret = removeElement(nums1, nums2, numsSize, 4);
for (int i = 0; i < ret; i++)
{
printf("%d ", nums2[i]);
}
return 0;
}
下面给出最优的思路：
思路3：
给两个指针destc;srcc;指向起始位置c;src找不是val的c;放到dest指向的位置c;时间复杂度：O(N)c;空间复杂度：O(1)
src指向数组外时停止c;然后返回destc;恰好就是删除val值后的数组
代码如下：
int removeElement(int *nums,int numsSize)
{
int src=0,dest=0;
while(src<numssize)
{
if(nums[src]==val)
{
src++;
}
else
{
nums[dest]=nums[src];
src++;
dest++;
}
}
return dest;
}
题目描述：
给你一个有序数组 nums c;请你 原地 删除重复出现的元素c;使每个元素 只出现一次 c;返回删除后数组的新长度。
不要使用额外的数组空间c;你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 c;并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 c; 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
题目来源：删除有序数组中的重复值
思路：
src找跟dest不相等的值c;没找到src++c;找到了c;dest++c;把src放入dest然后src++
代码如下：
int removeDuplicates(int* nums, int numsSize){
int src=0;
int dest=0;
if(numsSize==0)
{
return 0;
}
while(src<numsSize)
{
if(nums[src]==nums[dest])
{
src++;
}
else
{
dest++;
nums[dest]=nums[src];
src++;
}
}
return dest+1;//返回数组的长度
}
题目描述：
给你两个有序整数数组 nums1 和 nums2c;请你将 nums2 合并到 nums1 中c;使 nums1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + nc;这样它就有足够的空间保存来自 nums2 的元素。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1]
题目来源：合并两个数组
思路：
解法1：将nums2数据拷贝到nums1c;qsort快排nums1c;时间复杂度为(m+n)*log(m+n)
解法2：开辟一个m+n新数组c;归并两个小数组c;从头比较两个数组的值c;把小的放到新数组c;再拷贝到nums1c;时间复杂度O(M+N)c;空间复杂度O(m+n)
解法3：依次比较取大的从后往前放到nums1里面
这里我们讲解解法3：
经过上图分析c;代码如下：
void @H_572_184@merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i1 = m-1,i2 = n-1;
int dest=@H_960_183@m+n-1;
while(i1>=0 && i2>=0)//两个都大于等于0时继续
{
if(nums1[i1]>nums2[i2])//取大的放入nums1的后面
{
nums1[dest--]=nums1[i1--];
}
else
{
nums1[dest--]=nums2[i2--];
}
}
//如果是i2<0c;nums2拷贝结束c;那就处理结束了c;因为剩下的数本来就在Nums1里面
//如果是nums1结束c;得把nums2的数据挪过去
while(i2>=0)
{
nums1[dest--]=nums2[i2--];
}
}
需要注意的是：
如果是i2<0c;nums2拷贝结束c;那就处理结束了c;因为剩下的数本来就在Nums1里面
如果是nums1结束c;得把nums2的数据挪过去
我们OJ报错如何分析OJ程序？
题目描述：
题目来源：移除链表元素
思路一：把链表中所有不是val的值尾插到新链表中c;删除等于val的结点
思路解析：
此外我们需要考虑传进来的head为NULL的情况c;如果head为NULLc;我们直接返回NULL
思路一代码如下：
struct @H_724_2489@ListNode* removeElements(struct @H_724_2489@ListNode* head, int val)
{
if(head==NULL)
{
return NULL;
}
struct @H_724_2489@ListNode*newhead=NULL,*tail=NULL;//新链表的头节点和记录尾结点
//是val删除c;不是val尾插到新链表
struct @H_724_2489@ListNode*cur=head;
while(cur)
{
struct @H_724_2489@ListNode* next=cur->next;//便于找到当前结点的下一个结点c;定义一个next
if(cur->val==val)//是val删除
{
free(cur);
}
else//不是val进行尾插
{
//tail是NULL时c;说明没有元素
if(tail==NULL)//尾插第一个元素
{
newhead=cur;
tail=cur;
}
else
{
tail->next=cur;
tail=cur;
}
}
cur=next;
}
//当链表的最后一个结点的data是val时c;前一个结点不是val时c;我们将前一个结点尾插到新链表c;将最后一个结点删除时c;然而我们并没有将前一个结点的next置为NULLc;所以这里要将其置空;并且我们这里需要判断tail是不是NULLc;不是NULL我们才能进行此操作c;当链表的val值都是指定删除的val值时c;此时没有尾插进新链表元素c;此时tail为NULLc;就不能将tail的next置为NULL了
if(tail)
{
tail->next=NULL;
}
return newhead;
}
需要注意的是：
当链表的最后一个结点的data是val时c;前一个结点不是val时c;我们将前一个结点尾插到新链表c;将最后一个结点删除时c;然而我们并没有将前一个结点的next置为NULLc;所以这里要将其置空;并且我们这里需要判断tail是不是NULLc;不是NULL我们才能进行此操作c;当链表的val值都是指定删除的val值时c;此时没有尾插进新链表元素c;此时tail为NULLc;就不能将tail的next置为NULL了
思路二：cur找到val所在结点c;prev记录前一个结点c;进行链表的删除操作c;链表的删除操作需要找到删除的结点的前一个结点
struct @H_724_2489@ListNode* removeElements(struct @H_724_2489@ListNode* head, int val)
{
if (head == NULL)
{
return NULL;
}
struct @H_724_2489@ListNode* cur = head;
struct @H_724_2489@ListNode* prev = head;
while (cur)
{
while ( cur && (cur->val) != val )
{
prev = cur;//记录当前结点的前一个结点
cur = cur->next;
}
//while出来有两种情况1、cur为NULLc;说明走到结束了c;2、(cur->val) == valc;此时要删除
if(cur==NULL)
{
return head;
}
//找到val、删除
if (cur == head)//如果第一个就为val值c;头删
{
struct @H_724_2489@ListNode* newhead = cur->next;
free(cur);
cur = newhead;
head = newhead;
}
else//后面的删除
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
return head;
}
定义一个cur和prev来进行遍历c;prev记录cur的前一个结点c;cur不为空进循环c;然后再用一个循环来找是val值的结点c;while出来有两种情况：1、cur为NULLc;说明走到结束了c;2、(cur->val) == valc;此时要删除；所以接下来需要判断cur是不是NULLc;是NULL则直接返回headc;否则进行结点的删除c;删除又要分头删和不是头删的情况。
题目描述：
@H_616_2963@
题目来源：反转链表
思路一： 调整结点指针的方向c;n1和n2倒方向c;n3进行迭代
当n2为NULL时c;返回n1即可c;但是这里有一个问题c;将n2->next=n1c;我们怎么找n2的下一个结点呢？这里我们还需要用一个n3结点保存之前n2的next
struct @H_724_2489@ListNode* reverseList(struct @H_724_2489@ListNode* head)
{
if(head==NULL)
{
return NULL;
}
struct @H_724_2489@ListNode* n1,*n2,*n3;
n1=NULL;
n2=head;
n3=head->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)//当n3为NULL时c;n3就没有next了
{
n3=n3->next;
}
}
return n1;
}
思路二：
头插法c;定义一个新链表c;newhead=NULLc;原链表定义cur和nextc;next记录cur的下一个结点
struct @H_724_2489@ListNode* reverseList(struct @H_724_2489@ListNode* head)
{
if(head==NULL)
{
return NULL;
}
struct @H_724_2489@ListNode* cur=head;
struct @H_724_2489@ListNode* newhead=NULL;
struct @H_724_2489@ListNode* next=cur->next;
while(cur)
{
next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}
题目描述：
给定一个头结点为 head 的非空单链表c;返回链表的中间结点。
如果有两个中间结点c;则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点c;值分别为 3 和 4c;我们返回第二个结点。
题目来源：查找一个链表的中间结点
思路：
利用快慢指针
slow一次走1步
fast一次走2步
fast走到结尾时c;slow就走到了中间结点
但是当时偶数个结点呢？题目的要求是返回：如果有两个中间结点c;则返回第二个中间结点。
经过画图理解c;发现：
fast走到NULL时c;slow到达第二个中间结点。
故循环终止的条件应为fast不为NULL并且fast->next不为NULL
解题代码如下：
struct @H_724_2489@ListNode* @H_572_184@middleNode(struct @H_724_2489@ListNode* head)
{
if(head==NULL)
{
return NULL;
}
//快慢指针
struct @H_724_2489@ListNode* slow=head;
struct @H_724_2489@ListNode* fast=head;
while(fast&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
题目描述：
输入一个链表c;输出该链表中倒数第k个结点。
示例1
输入：
1,{1,2,3,4,5}返回值：
{5}
题目来源：查找一个链表的中间结点
思路：
和上面那个题一样c;我们先定义两个指针slowc;fastc;fast先走k步c;然后再一起走c;我们看下面的动图：
当fast为NULL时c;此时的slow就为倒数第k个结点
需要注意的是：输入的k如果大于结点的个数c;fast还没走完k步就变为NULL了c;这里要特别返回NULL
struct @H_724_2489@ListNode* FindKth@R_814_10586@il(struct @H_724_2489@ListNode* pListHead, int k )
{
if(k==0)
{
return NULL;
}
struct @H_724_2489@ListNode*slow,*fast;
slow=fast=pListHead;
//fast先走k步
while(k--)
{
if(fast==NULL)//输入的k大于结点的个数c;fast还没走完k步就变为NULL了
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
fast先走k步时c;要是输入的k大于结点的个数c;fast还没走完k步就变为NULL了c;这里要特别判断一下fast是不是等于NULLc;等于NULL直接返回NULL。
题目描述：
思路：取小的结点下来尾插到新链表
@H_967_3696@
由思路分析c;我们的代码如下：
struct @H_724_2489@ListNode* @H_572_184@mergeTwoLists(struct @H_724_2489@ListNode* l1, struct @H_724_2489@ListNode* l2)
{
//l1为NULLc;则返回l2
if(l1==NULL)
{
return l2;
}
//l2为NULLc;则返回l1
if(l2==NULL)
{
return l1;
}
struct @H_724_2489@ListNode*newhead=NULL;//新链表的头节点
struct @H_724_2489@ListNode*tail=NULL;//记录新链表的尾
struct @H_724_2489@ListNode* n1=l1;
struct @H_724_2489@ListNode* n2=l2;
while(n1&&n2)
{
//比较n1c;n2的valc;将小的尾插在新链表
if(n1->val<n2->val)
{
//新链表为NULL时c;即没有结点时
if(tail==NULL)
{
newhead=tail=n1;
}
//不为NULL时c;有结点时
else
{
tail->next=n1;
tail=n1;
}
n1=n1->next;//此时已经将较小的尾插进新链表c;这里进行迭代
}
else
{
if(tail==NULL)
{
newhead=tail=n2;
}
else
{
tail->next=n2;
tail=n2;
}
n2=n2->next;
}
//n1或者n2为NULL时结束
}
//将不为NULL的剩下的结点链接到新链表的尾
if(n1)
{
tail->next=n1;
}
if(n2)
{
tail->next=n2;
}
return newhead;
}
那么我们还能不能优化一下呢？
既然不管插n1还是n2我们第一次插进新链表时都要特殊处理c;那么我们可以先在外面先给它插一个结点进去c;这里就不用再循环里面if和else里面都要考虑没有结点时的尾插情况了c;代码如下：
struct @H_724_2489@ListNode* @H_572_184@mergeTwoLists(struct @H_724_2489@ListNode* l1, struct @H_724_2489@ListNode* l2)
{
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct @H_724_2489@ListNode*newhead=NULL;
struct @H_724_2489@ListNode*tail=NULL;
struct @H_724_2489@ListNode* n1=l1;
struct @H_724_2489@ListNode* n2=l2;
if(n1->val<n2->val)
{
newhead=tail=n1;
n1=n1->next;
}
else
{
newhead=tail=n2;
n2=n2->next;
}
while(n1&&n2)
{
if(n1->val<n2->val)
{
//尾插n1
tail->next=n1;
tail=n1;
n1=n1->next;
}
else
{
//尾插n2
tail->next=n2;
tail=n2;
n2=n2->next;
}
}
if(n1)
{
tail->next=n1;
}
if(n2)
{
tail->next=n2;
}
return newhead;
}
还有一种方法不需要考虑尾插时新链表为NULL的情况c;那就是我们设置一个带哨兵位的头结点c;下面我们介绍一下：
带哨兵位的头节点c;这个结点不存储有效数据c;函数永远不会修改到指向存储有效数据的第一个结点的指针plistc;因为拥有这个带哨兵位的头节点c;对在第一元素结点前插入结点和删除第一结点时c;其操作与其他结点的操作就统一了。
这个带哨兵位的头节点看起来简单一点c;为什么我们的单链表不设计这个结构呢？
这个头节点的结构在实际中很少出现c;包括哈希桶、邻接表做子结构都是不带头c;其次就是OJ中给的链表基本都是不带头的。
带哨兵位的头节点方法：
struct @H_724_2489@ListNode* @H_572_184@mergeTwoLists(struct @H_724_2489@ListNode* l1, struct @H_724_2489@ListNode* l2)
{
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct @H_724_2489@ListNode*newhead=NULL;
struct @H_724_2489@ListNode*tail=NULL;
newhead=tail=(struct @H_724_2489@ListNode*)@H_572_184@malloc(sizeof(struct @H_724_2489@ListNode));
while(l1&&l2)
{
if(l1->val<l2->val)
{
//尾插l1
tail->next=l1;
tail=l1;
l1=l1->next;
}
else
{
//尾插l2
tail->next=l2;
tail=l2;
l2=l2->next;
}
}
if(l1)
{
tail->next=l1;
}
if(l2)
{
tail->next=l2;
}
//return newhead->next;直接return这个会造成内存泄漏
struct @H_724_2489@ListNode* first = newhead->next;//将newhead的next先保存c;然后将newhead free
free(newhead);
return first;
}
需要注意的是c;我们最后要将这个开辟的带哨兵位的头结点需要释放掉c;否则会有内存泄漏c;我们需要返回newhead的nextc;那么我们先用first将newhead的next先保存c;然后将newhead free掉
题目描述：
现有一链表的头指针 ListNode pHeadc;给一定值xc;编写一段代码将所有小于x的结点排在其余结点之前c;且不能改变原来的数据顺序c;返回重新排列后的链表的头指针。*
思路：
1、把比x小的尾插入一个链表
2、把比x大的尾插入一个链表
3、再把两个链表链接在一起
@H_894_4618@
代码如下：
ListNode* partition(ListNode* pHead, int x)
{
// write code here
struct @H_724_2489@ListNode* LessHead=(struct @H_724_2489@ListNode*)@H_572_184@malloc(sizeof(struct @H_724_2489@ListNode));//较小值的带哨兵位头节点
struct @H_724_2489@ListNode* GreaterHead=(struct @H_724_2489@ListNode*)@H_572_184@malloc(sizeof(struct @H_724_2489@ListNode));//较大值的带哨兵位头节点
struct @H_724_2489@ListNode* LessTail=LessHead;
struct @H_724_2489@ListNode* GreaterTail=GreaterHead;
struct @H_724_2489@ListNode* cur = pHead;
while(cur)
{
if(cur->val<x)
{
//尾插到存放较小值的链表
LessTail->next=cur;
LessTail=cur;
}
else
{
//尾插到存放较大值的链表
GreaterTail->next=cur;
GreaterTail=cur;
}
cur=cur->next;
}
LessTail->next=GreaterHead->next;//链接
GreaterTail->next=NULL;
struct @H_724_2489@ListNode* first=LessHead->next;
free(LessHead);
LessHead=NULL;
free(GreaterHead);
GreaterHead=NULL;
return first;
}
题目描述：
对于一个链表c;请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法c;判断其是否为回文结构。
给定一个链表的头指针Ac;请返回一个bool值c;代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1 返回：true 1->2->3->2->1 返回：true
题目来源：链表的回文结构
思路1：
定义一个数组将链表中的val值都拷贝进去c;然后通过下标去比较第一个和最后一个是不是相等
bool chkPalindrome(ListNode* A) {
// write code here
int a[900];
struct @H_724_2489@ListNode* cur=A;
int n=0;
while(cur)
{
a[n++]=cur->val;
cur=cur->next;
}
int left=0;
int right=n-1;
while(left<right)
{
if(a[left]!=a[right])
{
return false;
}
left++;
right--;
}
return true;
}
这种解法空间复杂度为O(n)c;空间复杂度不符合要求c;但是牛客网给过了c;有些OJ题目c;有时间复杂度和空间复杂度的要求c;但是后台测试用例的检查对于时间复杂度和空间复杂度是不好检查的c;对于复杂度c;OJ系统通常检查的都不是很严格。这一块leetcode会严格一些c;牛客会更松散c;包括测试用例完整度c;也是这样的。
下面我们看一种正确的解法：
思路2：
1、先找到中间结点
2、将后半段逆置
3、比较前半段和后半段
找中间结点和逆置链表我们前面已经讲过了c;剩下的就是比较前半段和后半段了
代码如下：
struct @H_724_2489@ListNode* FindMidNode(struct @H_724_2489@ListNode* phead)//找到中间结点
{
struct @H_724_2489@ListNode*slow,fast;
slow=fast=phead;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next;
}
return slow;
}
//传一级指针c;用返回值返回头指针
/*struct ListNode* reverseList(struct ListNode* phead)//逆置链表
{
struct ListNode*cur=phead;
struct ListNode*newhead=NULL;
while(cur)
{
struct ListNode*next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
return newhead;
}*/
//传二级指针c;在函数里面修改头指针
void reverseList(struct @H_724_2489@ListNode** pphead)
{
struct @H_724_2489@ListNode*cur=pphead;
struct @H_724_2489@ListNode*newhead=NULL;
while(cur)//头插法逆置
{
struct @H_724_2489@ListNode*next=cur->next;
cur->next=newhead;
newhead=cur;
cur=next;
}
*pphead = newhead;
bool chkPalindrome(ListNode* A)
{
struct @H_724_2489@ListNode*@H_960_183@mid = FindMidNode(A);
//struct ListNode*rHead = reverseList(mid);
struct @H_724_2489@ListNode*rhead=@H_960_183@mid;
reverseList(&rhead);
struct @H_724_2489@ListNode*head=A;
while(rhead && head)
{
if(rhead->val!=head->val)
return false;
rhead=rhead->next;
head=head->next;
}
return true;
}
题目描述：
给你两个单链表的头节点 headA 和 headB c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点c;返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
题目来源：链表的相交
如何判断A、B链表是否相交？
思路1：
常规思路：A链表的每个结点依次和b链表的所有结点比较c;如果有相等c;就是交点c;时间复杂度O(N^2)
优化思路：分别算出A和B的长度c;lenA和lenBc;让长的先走|lenA-lenB|步c;再比较找交点c;时间复杂度O(N)
思路2：判断最后一个结点是否相同
题目要求我们返回相交的结点c;所以我们用思路1的优化思路来解这道题：
代码如下：
struct @H_724_2489@ListNode *geTintersectionNode(struct @H_724_2489@ListNode *headA, struct @H_724_2489@ListNode *headB) {
struct @H_724_2489@ListNode *curA = headA;
struct @H_724_2489@ListNode *curB = headB;
int lenB=0;
int lenA=0;
while(curA)//计算A的长度
{
lenA++;
curA=curA->next;
}
while(curB)//计算B的长度
{
lenB++;
curB=curB->next;
}
//假设A长B短
struct @H_724_2489@ListNode *longList=headA;
struct @H_724_2489@ListNode *shortList=headB;
if(lenA<lenB)
{
longList=headB;
shortList=headA;
}
//让长的先走差距步
int gap=abs(lenA-lenB);
while(gap--)
{
longList=longList->next;
}
//同时走c;找交点
while(longList && shortList)
{
if(longList == shortList)
{
return longList;//找到了返回
}
longList=longList->next;
shortList=shortList->next;
}
//表示不相交
return NULL;
}
首先我们计算出A、B链表的长度c;然后我们先假设长的链表为Ac;短的是Bc;然后如果lenA<lenB的话c;再将B赋给长链表c;A赋给短链表c;然后我们让长的先走差距步c;最后一起走然后找交点
问题描述：
给定一个链表c;判断链表中是否有环。
如果链表中有某个节点c;可以通过连续跟踪 next 指针再次到达c;则链表中存在环。 为了表示给定链表中的环c;我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1c;则在该链表中没有环。注意：pos 不作为参数进行传递c;仅仅是为了标识链表的实际情况。
如果链表中存在环c;则返回 true 。 否则c;返回 false 。
进阶：
你能用 O(1)（即c;常量）内存解决此问题吗？ 示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环c;其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环c;其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
题目来源：环形链表
思路：
快慢指针c;慢指针一次走一步。快指针一次走两步c;如果快指针能等于慢指针c;则是环形链表c;否则则不是
代码如下：
bool hasCycle(struct @H_724_2489@ListNode *head) {
struct @H_724_2489@ListNode *slow,*fast;
slow=fast=head;
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
面试提问：
解答：
一定可以追上c;slow进环时c;fast已经在环里面走了一定长度了c;那么这时在环里面就形成追赶c;fast去追slowc;假设slow进环时c;fast和slow之间的距离为Nc;环的大小为Cc;那么N一定小于C
fast和slow之间的距离变化是：
N,N-1,N-2,N-3…2,1,0
N最后一定会被缩小到0c;那么距离为0就一定相遇了
解答：
不一定能追上
假设slow一次走1步c;fast一次走3步c;slow进环时c;它们之间差距是Nc;环的长度是C
fast和slow之间的距离变化如下：
N,N-2,N-4,…,
slow和fast之间的距离是0的时候就追上了c;那么说明N是偶数c;就一定能追上
fast追到距离为-1时c;此时它们的距离为C-1c;C-1也是奇数时c;就永远追不上
总结：fast一次走xc;slow一次走y步都是可以的c;最重要的是c;追赶过程中的步差为x-yc;步差为1就一定能追上c;其他不一定能追上
题目描述：
给定一个链表c;返回链表开始入环的第一个节点。 如果链表无环c;则返回 null。
为了表示给定链表中的环c;我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1c;则在该链表中没有环。注意c;pos 仅仅是用于标识环的情况c;并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
题目来源：环形链表Ⅱ
解题思路1：
证明：
假设：链表头到入口点的距离是Lc;相遇点到入口点的距离是Xc;环的长度为Cc;
慢指针走的路程是L+X
快指针走的路程是L+C+X
2(L+X)=L+C+X得L=C-X*
很多文章的证明是这个c;但是这个证明是错的c;因为Slow进环之前c;fast不一定在环里面只走了一圈
正确的证明
相遇时：慢指针走的路程L+X
快指针走的路程L+NC+X（N>=1）
2(L+X)=L+NC+X
L+X=NC
L=NC-X
L=(N-1)C+C-X
结论：一个指针从相遇点开始走c;一个指针从head走c;它们会在入口点相遇
解题思路2：
代码如下：
struct @H_724_2489@ListNode* geTintersectionNode(struct @H_724_2489@ListNode* headA, struct @H_724_2489@ListNode* headB) {
//1、计算A、B长度
struct @H_724_2489@ListNode*curA = headA;
struct @H_724_2489@ListNode*curB = headB;
int lenA=0;
int lenB=0;
while(curA)
{
lenA++;
curA=curA->next;
}
while(curB)
{
lenB++;
curB=curB->next;
}
//2、计算长度差值c;长的先走差值步
int gap = abs(lenA-lenB);
struct @H_724_2489@ListNode* longList = headA;
struct @H_724_2489@ListNode* shortList = headB;
if(lenA<lenB)
{
longList = headB;
shortList = headA;
}
while(gap--)
{
longList=longList->next;
}
//3、然后一起走
while(longList && shortList)
{
if(longList==shortList)
{
return longList;
}
longList=longList->next;
shortList=shortList->next;
}
return NULL;
}
struct @H_724_2489@ListNode *detectCycle(struct @H_724_2489@ListNode *head) {
struct @H_724_2489@ListNode *slow=head;
struct @H_724_2489@ListNode *fast=head;
while(fast &&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
//相遇了
struct @H_724_2489@ListNode *@H_960_183@meet=slow;
struct @H_724_2489@ListNode *next=@H_960_183@meet->next;//记录相遇点的下一个节点
meet->next=NULL;//断开相遇点
return geTintersectionNode(head,next);
}
}
return NULL;
}
记录meet的nextc;然后从next开始和head开始判断是否相交c;相交的话返回交点c;回到了我们之前讲的相交链表那个题
题目描述：
给你一个长度为 n 的链表c;每个节点包含一个额外增加的随机指针 random c;该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成c;其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点c;并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如c;如果原链表中有 X 和 Y 两个节点c;其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y c;同样有 x.random --> y 。
返回复制链表的头节点。 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
示例 1
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = [] 输出：[] 解释：给定的链表为空（空指针）c;因此返回 null。
题目来源：复制带随机指针的链表
思路1：
1、先复制原链表的每个节点c;将复制好的新节点链接起来
2、求出原链表中每个结点cur的random和cur的相对距离
再去复制新链表到当前节点相对距离的结点c;赋值给randomc;找每个节点的random时间复杂度是O(N)c;N个节点就是O(N^2)——效率低
思路2：
1、在原链表的每个节点的后面c;链接插入一个拷贝节点
2、置random
代码如下：
struct @H_724_2489@Node* copyRandomList(struct @H_724_2489@Node* head) {
if(head==NULL)
{
return NULL;
}
//1、每个节点的拷贝链接在该节点后面
struct @H_724_2489@Node* cur=head;
while(cur)
{
struct @H_724_2489@Node* next = cur->next;
struct @H_724_2489@Node* copy = (struct @H_724_2489@Node*)@H_572_184@malloc(sizeof(struct @H_724_2489@Node));
copy->val=cur->val;
cur->next=copy;
copy->next=next;
cur=next;
}
//2、置random
cur=head;
while(cur)
{
struct @H_724_2489@Node* copy=cur->next;
if(cur->random)
{
copy->random = cur->random->next;
}
else
{
copy->random=NULL;
}
cur=copy->next;
}
//3、剪切拷贝的节点c;尾插到新链表
cur=head;
struct @H_724_2489@Node* newhead,*tail;
newhead=tail=(struct @H_724_2489@Node*)@H_572_184@malloc(sizeof(struct @H_724_2489@Node));
while(cur)
{
struct @H_724_2489@Node* copy=cur->next;
struct @H_724_2489@Node* next=copy->next;
tail->next=copy;
tail=copy;
cur->next=next;
cur=next;
}
struct @H_724_2489@Node* first=newhead->next;
free(newhead);
newhead=NULL;
return first;
}
将每个节点的拷贝链接在该节点后面相当于链表当中的插入操作c;每个拷贝结点都在原结点的后面c;原结点和拷贝结点就建立了一个相对关系c;我们可以发现我们很容易就能找到拷贝结点的random在哪c;他就是cur->random->nextc;然后通过相对位置置拷贝的结点randomc;最后将拷贝的结点尾插到新链表c;这里我们对新链表使用了带哨兵位的头结点。
以上就是博主关于复杂度、数组、链表的热门OJ的讲解c;期待你的点赞哦！欢迎大家学习讨论c;如有错误c;希望大家评论区留言。
以上是大佬教程为你收集整理的数据结构之超硬核热门复杂度、数组、链表OJ题2W+文字+图片详解全部内容，希望文章能够帮你解决数据结构之超硬核热门复杂度、数组、链表OJ题2W+文字+图片详解所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。