临沂网站建设技术托管,公司人员管理系统,东莞网站建设要注意什么,沈阳妇科大夫排行前言#xff1a; 在计算机科学中#xff0c;数组和链表是两种常见的数据结构#xff0c;用于存储和组织数据。它们分别具有不同的特点和适用场景。 本博客将深入讨论数组和链表在OJ题目中的应用。我们将从基本概念开始#xff0c;介绍数组和链表的定义和特点#xff0c;并…前言 在计算机科学中数组和链表是两种常见的数据结构用于存储和组织数据。它们分别具有不同的特点和适用场景。 本博客将深入讨论数组和链表在OJ题目中的应用。我们将从基本概念开始介绍数组和链表的定义和特点并分析它们在不同场景下的优势和劣势。 接下来我们将探讨数组在OJ题目中的常见应用。我们将介绍如何原地移除数组中所有的val元素如何删除排序数组中的重复项以及如何合并两个有序数组。 随后我们将探讨链表在OJ题目中的常见应用。我们将介绍如何删除链表中值为val的所有节点如何翻转单链表如何返回链表的中间结点和倒数第k个结点以及如何合并两个有序链表等。 此外我们还将介绍一些更复杂的链表问题如链表的分割、回文链表、相交链表、带环链表等。我们将详细讲解每个问题的解题思路和实现方法。 最后我们将讨论带有随机指针的链表介绍如何复制这种特殊的链表结构并解决相关问题。 通过对这些数组和链表的OJ题目的探讨我们将加深对数组和链表的理解并学会在实际问题中灵活运用它们。希望本博客能帮助读者更好地掌握这两种数据结构并提升解题能力。让我们开始吧 个人主页Oldinjuly的个人主页 收录专栏数据结构 欢迎各位点赞收藏⭐关注❤️ 目录
一、数组
1.原地移除数组中所有的val元
2.删除排序数组中的重复项
3.合并两个有序数组
二、链表
1.删除链表中值为val的所有节点
2.翻转单链表
3.返回中间结点
4.返回倒数第k个结点
6.链表分割 7.回文链表
8.相交链表
9.带环链表Ⅰ
10.带环链表Ⅱ
11.复制带随机指针的链表 一、数组
1.原地移除数组中所有的val元素
方法一暴力删除,挪动数据覆盖: 时间复杂度O(N^2), 空间复杂度O(1)
方法二开辟新空间tmp设置两个“指针”dst和srcnums[src]不等于val的直接插入到tmp[dst]中等于val的直接跳过然后tmp拷贝到nums中。 int removeElement(int* nums, int numsSize, int val)
{int* tmp (int*)malloc(sizeof(int)*numsSize);int dst0,src0;while(srcnumsSize){if(nums[src]!val){tmp[dst]nums[src];}else{src;}}memcpy(nums,tmp,sizeof(int)*dst);return dst;
}方法三双指针在原数组上直接覆盖
nums[src]不等于val直接覆盖尾插到dst位置dstsrc。
nums[src]等于val直接src相当于删除。
int removeElement(int* nums, int numsSize, int val)
{int dst0,src0;while(src numsSize){if(nums[src] ! val){nums[dst] nums[src];}else{src;}}return dst;
}2.删除排序数组中的重复项
双指针dst和src
dst和src如果相等src。
dst和src如果不相等dst先然后src覆盖到dst上src再。
int removeDuplicates(int* nums, int numsSize)
{int dst0, src0;while(srcnumsSize){if(nums[dst]nums[src]){src;}else{nums[dst]nums[src];}}return dst;
} 3.合并两个有序数组
1.从前往后归并需要开新空间 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int* tmp (int*)malloc(sizeof(int)*(mn));int begin10, begin20, pos0;while(begin1 m begin2 n){if(nums1[begin1] nums2[begin2]){tmp[pos]nums1[begin1];}else{tmp[pos]nums2[begin2];}}while(begin1 m){tmp[pos]nums1[begin1];}while(begin2 n){tmp[pos]nums2[begin2];}memcpy(nums1,tmp,sizeof(int)*(mn));free(tmp);
}2.从后往前归并不需要开新空间 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1m-1,end2n-1,endmn-1;while(end10end20){if(nums1[end1]nums2[end2]){nums1[end--]nums1[end1--];}else{nums1[end--]nums2[end2--];}}while(end20){nums1[end--]nums2[end2--];}
}二、链表
1.删除链表中值为val的所有节点
解法一在原链表上进行操作 struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur head;struct ListNode* prev NULL;while(cur){if(cur-val val){if(cur head){head cur-next;free(cur);cur head;}else{prev-next cur-next;free(cur);cur prev-next;}}else{prev cur;cur cur-next;}}return head;
}注意头删不需要prev节点是要单独讨论的。 解法二创建一个新链表 struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* newhead NULL, *tail NULL, *cur head;while(cur){if(cur-val val){struct ListNode* next cur-next;free(cur);cur next; }else {if(newhead NULL){newhead cur;tail cur;}else{tail-next cur;tail tail-next;}cur cur-next;}}if(tail){tail-next NULL;}return newhead;
}注意 逻辑上的一个新链表但是内存没有额外开辟空间。避免每次重复找尾结点设置一个tail指针变量来记录。最后要给tail的next置空。 2.翻转单链表
解法一三指针链接法 struct ListNode* reverseList(struct ListNode* head)
{struct ListNode *n1, *n2, *n3;n1 NULL;n2 head;if(head)n3 head-next;while(n2){n2-next n1;n1 n2;n2 n3;if(n3)n3 n3-next;} return n1;
}问题为什么设置三个指针变量进行迭代 如果只设置两个指针变量进行迭代n1赋值n2的next域之后n2就无法迭代带原本的next域而三个指针变量可以解决这个问题。 注意n3进行迭代之前要判断n3是否为NULL。 解法二头插法 struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead NULL;struct ListNode* cur head;while(cur){struct ListNode* next cur-next;cur-next newhead;newhead cur;cur next;}return newhead;
}3.返回中间结点
双指针快慢指针fast指针走两步slow指针走一步
奇数个链表节点fast NULLslow对应中间结点
偶数个链表结点fast-next NULLslow对应中间节点 struct ListNode* middleNode(struct ListNode* head)
{struct ListNode *slow head, *fast head;while(fast fast-next){fast fast-next-next;slow slow-next;}return slow;
}4.返回倒数第k个结点
双指针
fast指针先走k步然后两个指针一起走fast走到NULLslow走到目标节点。
fast指针先走k-1步然后两个指针一起走fast走到尾结点slow走到目标节点。 struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{struct ListNode *fast head, *slow head;int i 0;for(i0;ik;i) {//链表没有k步长那么倒数就是空if(!fast)return NULL;fast fast-next;}/*while(k--)//k--走k步--k走k-1步{if(!fast)return NULL;fast fast-next;}*/while(fast){fast fast-next;slow slow-next;}return slow;
}5.合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode *head NULL, *tail NULL;if(!list1)return list2;if(!list2)return list1;while(list1 list2){if(list1-val list2-val){if(head NULL){head list1;tail list1;}else{tail-next list1;tail tail-next;}list1 list1-next;}else{if(head NULL){head list2;tail list2;}else{tail-next list2;tail tail-next;}list2 list2-next;}}if(list1){tail-next list1;}if(list2){tail-next list2; }return head;
}注意 while循环的条件是list1list2循环里面是继续条件但是我们心中想的是循环终止条件也就是有一个链表结束循环也就结束。当循环结束后只需要把 没有遍历到空的链表尾接到tail后面即可。 这题合并有序链表和合并有序数组都使用了一个关键思想归并这也是排序算法的一个重要思想。 代码优化
这里的归并使用了尾插不带头结点单链表的尾插有一个缺点就是第一次插入不需要找tail直接赋值给head即可需要单独讨论为了使代码简洁此时就需要另一种链表带头结点哨兵位的单链表。
头结点什么数据也不存储那么这个头结点有什么意义呢
尾插尾删不需要单独讨论形成统一化。不需要传二级指针了改的是头结点的next修改结构体直接传结构体指针即可。 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(!list1)return list2;if(!list2)return list1;struct ListNode* head (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail head;while(list1 list2){if(list1-val list2-val){tail-next list1;tail tail-next;list1 list1-next;}else{tail-next list2;tail tail-next;list2 list2-next;}}if(list1)tail-next list1;if(list2)tail-next list2;struct ListNode* next head-next;free(head);head next;return head;
}6.链表分割
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode *lHead, *lTail, *gHead, *gTail;lHead lTail (ListNode*)malloc(sizeof(ListNode));gHead gTail (ListNode*)malloc(sizeof(ListNode));ListNode* cur pHead;while(cur){if(cur-val x){lTail-next cur;lTail lTail-next;}else{gTail-next cur;gTail gTail-next;}cur cur-next;}lTail-next gHead-next;//不置空可能会出现环gTail-next NULL;ListNode* next lHead-next;free(lHead);free(gHead); return next; }
}; 注意 该题开辟了两个链表头结点lessHeadgreaterHeadlessHead存放比x小的节点greaterHead存放大于等于x的节点。这题最好使用带头结点的单链表原因如果不带头结点lessHead为空或者greaterHead为NULL的话此时链接两个链表lTail-next gHead-next这句代码就会出错。greaterTail的next的要置空否则会出现环。 7.回文链表
思路 对于链表1-2-3-2-1-NULL想判断是否回文可以先将链表后半部分3-2-1-NULL进行逆置变成1-2-3-NULL;然后前半部分和后半部分进行比较全部相等就是回文链表。
这里要复用之前的两个题目的函数返回中间节点和翻转单链表。 struct ListNode* middleNode(struct ListNode* head)
{struct ListNode *slow head, *fast head;while(fast fast-next){fast fast-next-next;slow slow-next;}return slow;
}struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead NULL;struct ListNode* cur head;while(cur){struct ListNode* next cur-next;cur-next newhead;newhead cur;cur next;}return newhead;
}bool isPalindrome(struct ListNode* head)
{struct ListNode* headA head;struct ListNode* headB middleNode(head);struct ListNode* curA headA;struct ListNode* curB reverseList(headB);;while(curA curB){if(curA-val ! curB-val)return false;curA curA-next;curB curB-next;}return true;
}8.相交链表
补充相交链表
上一道题目回文链表中后半部分逆置过后的链表其实就是相交链表。
相交链表是这样的 而不是这样
解法一暴力遍历headA的每一个节点都和headB的每一个节点比较比较的是节点指针不能比较val时间复杂度ON^2。
解法二
先遍历两个链表得到两个链表的长度先判断尾结点是否相等如果不相等一定不是相交链表
再算出长度差让长的先走长度差步然后一起走第一个相等的就是公共结点。 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode *curA headA, *curB headB;int lenA 1, lenB 1;while(curA-next)//这里是为了找到尾结点所以len初始化成1{curA curA-next;lenA;} while(curB-next){curB curB-next;lenB;}//不相交if(curA ! curB)return NULL; int dis abs(lenA - lenB);struct ListNode *longList headA, *shortList headB;if(lenA lenB){longList headB;shortList headA;}while(dis--){longList longList-next;}while(longList ! shortList){longList longList-next;shortList shortList-next;}return longList;
}9.带环链表Ⅰ
这题也可以用快慢指针来解决
fast指针一次走两步
slow指针一次走两步
在两个指针都进环后他们在环中的某个位置一定能相遇为什么呢这要用相对运动的思想来分析一下了 我们可以把带环链表进行抽象化便于分析 首先fast指针一定比slow指针先入环 slow指针入环后fast指针开始追赶slow指针只是典型的追击问题假设slow入环后两者距离为N。 slow走一步fast走两步每追击一次两者的距离缩短1。两者的距离变化N-N-1-N-2-...-1-0综上两者的距离最终为0会相遇。 bool hasCycle(struct ListNode *head)
{struct ListNode *fast head, *slow head;while(fast fast-next){slow slow-next;fast fast-next-next;if(fast slow)return true; }return false;
}思考如果fast一次走三步、四步他们会在环中相遇吗
答案是不一定
分析
所以初始距离M和C-1均为奇数的话他们永不相遇fast一次走四步也是一样的道理综上fast最好的步数就是两步。
10.带环链表Ⅱ
解法一需要一些数学知识来分析 struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *slow head, *fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(fast slow){struct ListNode* meet slow;struct ListNode* cur head;while(cur ! meet){cur cur-next;meet meet-next;}return cur;}}return NULL;
} 解法二相交链表法
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode *curA headA, *curB headB;int lenA 1, lenB 1;while(curA-next)//这里是为了找到尾结点所以len初始化成1{curA curA-next;lenA;} while(curB-next){curB curB-next;lenB;}//不相交if(curA ! curB)return NULL; int dis abs(lenA - lenB);struct ListNode *longList headA, *shortList headB;if(lenA lenB){longList headB;shortList headA;}while(dis--){longList longList-next;}while(longList ! shortList){longList longList-next;shortList shortList-next;}return longList;
}struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *fast head, *slow head;while(fast fast-next){slow slow-next;fast fast-next-next;if(fast slow){struct ListNode* meet slow;struct ListNode* newhead meet-next;meet-next NULL;return getIntersectionNode(head,newhead);}} return NULL;
} 11.复制带随机指针的链表
分析所谓深拷贝就是malloc出新的节点然后把原始结点的数据赋值到新结点中。并且新链表随机指针的链接关系要和原链表的链接关系相同。 方法一首先拷贝原链表的结点得到一个新链表然后记录每个结点和他random域结点的相对位置或者给每个节点设置一个索引值。通过相对位置来调整新链表的random域的链接关系。注意一定不能通过原链表的random域的值来进行链接否则拷贝链表中的指针会指向原链表中。 时间复杂度ON^2 方法二让拷贝结点插入到原节点的后面然后置每个拷贝节点的random域最后把拷贝结点给解下来并恢复原链表。 struct Node* copyRandomList(struct Node* head)
{//拷贝结点插入到原节点的后面struct Node* cur head;while(cur){struct Node* next cur-next;struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;cur-next copy;copy-next next;cur next;} //置一下拷贝节点的random域cur head;while(cur){struct Node* copy cur-next;if(cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur copy-next;}//把拷贝结点尾插下来并且恢复原结点cur head;struct Node *copyhead NULL, *copytail NULL;while(cur){struct Node *copy cur-next, *next copy-next;//copy节点尾插到新链表if(copyhead NULL){copyhead copytail copy;}else{copytail-next copy;copytail copytail-next;}//恢复原链表cur-next next;cur next;}return copyhead;
}
