数据结构—顺序表超经典算法
数据结构—顺序表链表经常用到的算法
所有题目链接
移除元素
删除有序数组中的重复项
合并两个有序数组
移除链表元素
反转链表
链表的中间节点
合并两个有序链表
链表分割
链表的回文结构
相交链表
环形链表I
环形链表II
顺序表算法题（双指针法）
移除元素
题目链接↓
移除元素
题目讲解↓
思路：双指针法，创建两个变量dst,src如果src指向的数据是val，src++如果src指向的数据不是val，赋值(src给dst)，src和dsr都++src在前面探路（找非val值），dst在后面站岗（保存非val值）
时间复杂度：O(N)
空间复杂度：O(1)
//1.移除元素intremoveElement(int* nums,int numsSize,int val){//创建两个变量int src =0, dst =0;;while(src < numsSize){//src指向的数据是val，src++//src指向的数据不是val，赋值整体再++if(nums[src]!= val){ nums[dst]= nums[src]; dst++;} src++;}return dst;}
删除有序数组中的重复项
题目链接↓
删除有序数组中的重复项
题目讲解↓
思路：双指针法，创建两个变量，分别指向数组起始和下一个位置如果src的值和dst的值相等，src++如果src的值和dst的值不相等，dst++，src赋值给dst，src++
时间复杂度：O(N)
空间复杂度：O(1)
//2.删除有序数组中的重复项intremoveDuplicates(int* nums,int numsSize){//创建两个变量 分别指向数组起始和下一个位置int src =1, dst =0;//src的值和dst的值相等，src++ //src的值和dst的值不相等，dst++，src赋值给dst，src++ while(src < numsSize){if(nums[src]!= nums[dst]){ dst++; nums[dst]== nums[src];} src++;}return dst +1;}//优化:如果 ++dst == src，就会造成自己给自己赋值，因此优化一下intremoveDuplicates(int* nums,int numsSize){//创建两个变量 分别指向数组起始和下一个位置int src =1, dst =0;//src的值和dst的值相等，src++ //src的值和dst的值不相等，dst++，src赋值给dst，src++ while(src < numsSize){if(nums[src]!= nums[dst]&&++dst != src){ nums[dst]== nums[src];} src++;}return dst +1;}
合并两个有序数组
题目链接↓
合并两个有序数组
题目讲解↓
思路：从后往前遍历数组，找大（谁大谁先往后放）
时间复杂度O(N)
//3.合并两个有序数组voidmerge(int* nums1,int nums1Size,int m,int* nums2,int nums2Size,int n){//创建三个变量int l1 = m -1, l2 = n -1, l3 = m + n -1;while(l1 >=0&& l2 >=0){//比较谁大，谁往后放if(nums1[l1]> nums2[l2]){ nums1[l3--]= nums1[l1--];}else{ nums1[l3--]= nums2[l2--];}}//l1越界（需要特殊处理）while(l2 >=0){ nums1[l3--]= nums2[l2--];}//l2越界（不需要处理）//不会同时越界}
链表算法题（快慢指针，三指针法，创建新链表法）
移除链表元素
题目链接↓
移除链表元素
题目讲解↓
思路：创建新链表，将原链表中不为val的节点拿下来尾插
时间复杂度：O(N)
空间复杂度：O(1)
此处创建新链表菲真创建新链表，而是通过修改原本的链表 \color{red}{此处创建新链表菲真创建新链表，而是通过修改原本的链表} 此处创建新链表菲真创建新链表，而是通过修改原本的链表
//4.移除链表元素/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNode ListNode;structListNode*removeElements(structListNode* head,int val){ ListNode* newHead,* newTail; newHead = newTail =NULL; ListNode* pcur = head;while(pcur){//判断pcur节点的值是否为valif(pcur->val != val){//尾插 分类（链表是否为空）if(newHead ==NULL){//链表为空 newHead = newTail = pcur;}else{//链表非空 newTail->next = pcur; newTail = pcur;}} pcur = pcur->next;}//最后别忘了把尾节点的next置为空，不然会把剩下的节点带过来if(newTail){ newTail->next =NULL;}return newHead;}反转链表
题目链接↓
反转链表
题目讲解↓
思路1：创建新链表，遍历原链表将节点头插到新链表中
此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个， \color{red}{此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，} 此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，
因此要格外注意保存下一个节点和尾节点的 n e x t 为 N U L L \color{red}{因此要格外注意保存下一个节点和尾节点的next为NULL} 因此要格外注意保存下一个节点和尾节点的next为NULL
时间复杂度O(N)
空间复杂度O(1)
思路2：创建三个指针，改变指针的指向
时间复杂度O(N)
空间复杂度O(1)
//5.反转链表typedefstructListNode ListNode;structListNode*reverseList(structListNode* head){ ListNode* pcur = head; ListNode* newHead = head;while(pcur){//头插 ListNode* next = pcur->next;//保存下一个节点 pcur->next = newHead; newHead = pcur; pcur = next;}if(head)//注意尾节点，避免成环{ head->next =NULL;}return newHead;}typedefstructListNode ListNode;structListNode*reverseList(structListNode* head){if(head ==NULL)//需要处理一下特殊情况{returnNULL;}//创建三个指针 ListNode* n1,* n2,* n3; n1 =NULL, n2 = head, n3 = n2->next;while(n2){ n2->next = n1; n1 = n2; n2 = n3;if(n3){ n3 = n3->next;}}return n1;}
链表的中间节点
题目链接↓
链表的中间节点
题目讲解↓
思路：快慢指针，慢指针每次走一步，快指针每次走两步
时间复杂度：O(N)
- 画出思路
//6.链表的中间节点/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNode ListNode;structListNode*middleNode(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast !=NULL&& fast->next !=NULL)//用到短路（方向不能反，否则空指针解引用）{ slow = slow->next; fast = fast->next->next;}return slow;}
合并两个有序链表
题目链接↓
合并两个有序链表
题目讲解↓
思路：创建新链表，遍历并比较原链表中节点的值，小的尾插到新链表中
此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个， \color{red}{此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，} 此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，
因此要格外注意保存下一个节点和尾节点的 n e x t 为 N U L L \color{red}{因此要格外注意保存下一个节点和尾节点的next为NULL} 因此要格外注意保存下一个节点和尾节点的next为NULL
时间复杂度：O(N)
//7.合并两个有序链表/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNode ListNode;structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(list1 ==NULL){return list2;}if(list2 ==NULL){return list1;}//创建空链表 ListNode* newHead,* newTail; newHead = newTail =NULL;//遍历原链表 ListNode* l1 = list1; ListNode* l2 = list2;while(l1 !=NULL&& l2 !=NULL){if(l1->val < l2->val){//l1尾插if(newHead ==NULL){//空链表 newHead = newTail = l1;}else{//非空链表 newTail->next = l1; newTail = newTail->next;} l1 = l1->next;//保存下一个节点}else{//l2尾插if(newHead ==NULL){//空链表 newHead = newTail = l2;}else{//非空链表 newTail->next = l2; newTail = newTail->next;} l2 = l2->next;}}//l1为空，l2为空if(l1){ newTail->next = l1;}if(l2){ newTail->next = l2;}return newHead;}
- 以上的代码有些冗余（if判断NULL太多)，如果创捷一个哨兵位可以更加简洁
typedefstructListNode ListNode;structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(list1 ==NULL){return list2;}if(list2 ==NULL){return list1;}//创建空链表 ListNode* newHead,* newTail; newHead = newTail =(ListNode*)malloc(sizeof(ListNode));//申请哨兵位//遍历原链表 ListNode* l1 = list1; ListNode* l2 = list2;while(l1 !=NULL&& l2 !=NULL){if(l1->val < l2->val){//l1尾插 newTail->next = l1; newTail = newTail->next; l1 = l1->next;//保存下一个节点}else{//l2尾插 newTail->next = l2; newTail = newTail->next; l2 = l2->next;}}//l1为空，l2为空if(l1){ newTail->next = l1;}if(l2){ newTail->next = l2;} ListNode* retHead = newHead->next;free(newHead); newHead =NULL;return retHead;}
链表分割
题目链接↓
链表分割
题目讲解↓
思路:创建两个链表(小链表、大链表)，遍历原链表，小的尾插到小链表中，大的尾插到大链表中，大链表和小链表首尾相连
此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个， \color{red}{此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，} 此处创建新链表菲真创建新链表，通过不断拆解这两个链表合为一个，
因此要格外注意保存下一个节点和尾节点的 n e x t 为 N U L L \color{red}{因此要格外注意保存下一个节点和尾节点的next为NULL} 因此要格外注意保存下一个节点和尾节点的next为NULL
//8.链表分割/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/classPartition{public: ListNode*partition(ListNode* pHead,int x){//创建两个带哨兵位的空链表 ListNode* lessHead,* lessTail; lessHead = lessTail =(ListNode*)malloc(sizeof(ListNode)); ListNode* greatHead,* greatTail; greatHead = greatTail =(ListNode*)malloc(sizeof(ListNode)); ListNode* pcur = pHead;while(pcur){if(pcur->val < x){ lessTail->next = pcur; lessTail = lessTail->next;}else{ greatTail->next = pcur; greatTail = greatTail->next;} pcur = pcur->next;}//大链表尾节点的next指针置为NULL(避免链表成环) greatTail->next =NULL;//大小链表首尾相连 lessTail->next = greatHead->next; ListNode* ret = lessHead->next;free(lessHead);free(greatHead);return ret;}};
链表的回文结构
题目链接↓
链表的回文结构
题目讲解↓
思路1:创建数组(大小900)，遍历链表将节点的值依次存储在数组中，若数组为回文结构，则链表为回文结构
思路2:找链表中间节点，将中间节点作为新链表的头节点，反转链表遍历原链表和反转后链表节点的值是否相等
中间节点->快慢指针
反转链表->三指针法
前面都讲过
- 思路1
//9.链表的回文结构 bool chkPalindrome(ListNode* A){int arr[900]={0};//遍历链表，将链表中节点的值依次存储到数组中 ListNode* pcur = A;int i =0;while(pcur){ arr[i++]= pcur->val; pcur = pcur->next;}//判断数组是否为回文结构int left =0, right = i -1;while(left < right){if(arr[left]!= arr[right])return false; left++; right--;}return true;}
- 思路2
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/classPalindromeList{public://找中间节点structListNode*middleNode(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast !=NULL&& fast->next !=NULL)//用到短路（方向不能反，否则空指针解引用）{ slow = slow->next; fast = fast->next->next;}return slow;}//反转链表structListNode*reverseList(structListNode* head){if(head ==NULL)//需要处理一下特殊情况{returnNULL;}//创建三个指针 ListNode* n1,* n2,* n3; n1 =NULL, n2 = head, n3 = n2->next;while(n2){ n2->next = n1; n1 = n2; n2 = n3;if(n3){ n3 = n3->next;}}return n1;}boolchkPalindrome(ListNode* A){//1.找中间节点 ListNode* mid =middleNode(A);//2.反转以中间节点为头的链表 ListNode* right =reverseList(mid);//3.遍历原链表和反转后的链表，比较节点的值是否相等 ListNode* left = A;while(right){if(left->val != right->val)returnfalse; left = left->next; right = right->next;}returntrue;}};用到的都是前面讲的方法
相交链表
题目链接↓
相交链表
题目讲解↓
思路：求两个链表的长度，长链表先走长度差步，长短链表开始同步遍历，找相同的节点两个链表的尾节点相同，两个链表一定相交
不相交
先了解相交链表的几种情况
//10.相交链表typedefstructListNode ListNode;structListNode*getIntersectionNode(structListNode* headA,structListNode* headB){//求链表的长度 ListNode* pa = headA; ListNode* pb = headB;int sizeA =0, sizeB =0;while(pa){++sizeA; pa = pa->next;}while(pb){++sizeB; pb = pb->next;}//求长度差int gap =abs(sizeA - sizeB);//求绝对值//定义长短链表（假设法） ListNode* shortList = headA; ListNode* longList = headB;if(sizeA > sizeB){ longList = headA; shortList = headB;}//让长链表先走gapwhile(gap--){ longList = longList->next;}//shortList longList在同一起跑线while(shortList)//或者用while(longList){if(shortList == longList){return shortList;} shortList = shortList->next; longList = longList->next;}//链表不相交returnNULL;}
环形链表（快慢指针）
环形链表I
题目链接↓
环形链表I
题目讲解↓
思路：快慢指针，慢指针每次走一步，快指针每次走两步
如果slow和fast指向同一个节点，说明链表带环
typedefstructListNode ListNode; bool hasCycle(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast && fast->next){ slow = slow->next; fast = fast->next->next;if(slow == fast){//相遇return true;}}//链表不带环return false;}
- 思考1：为什么快指针每次⾛两步，慢指针⾛⼀步可以相遇，有没有可能遇不上，请推理证明！
slow⼀次⾛⼀步，fast⼀次⾛2步，fast先进环，假设slow也⾛完⼊环前的距离，准备进环，此时fast和slow之间的距离为N，接下来的追逐过程中，每追击一次，他们之间的距离缩小1步追击过程中fast和slow之间的距离变化：
因此，在带环链表中慢指针走⼀步，快指针走两步最终⼀定会相遇。
- 思考2：快指针⼀次走3步，走4步，…n步行吗?
step1:
按照上⾯的分析，慢指针每次⾛⼀步，快指针每次⾛三步，此时快慢指针的最⼤距离为N，接下来的
追逐过程中，每追击⼀次，他们之间的距离缩⼩2步
追击过程中fast和slow之间的距离变化：
分析:
1、如果N是偶数，第⼀轮就追上了
2、如果N是奇数，第⼀轮追不上，快追上，错过了，距离变成-1，即C-1，进⼊新的⼀轮追击
a、C-1如果是偶数，那么下⼀轮就追上了
b、C-1如果是奇数，
那么就永远都追不上
总结⼀下追不上的前提条件：
N是奇数，C是偶数
step2:
假设：
环的周长为 C，头结点到slow结点的长度为
L，slow走一步，fast走三步，当slow指针入环后，slow和fast指针在环中开始进行追逐，假设此时fast指针已经绕环 x 周。
在追逐过程中，快慢指针相遇时所走的路径长度：
• fast：L + xC + C - N • slow：L 由于慢指针走一步，快指针要走三步，因此得出：3 *{慢指针路程} =
{快指针路程}，即：
3L = L + xC + C - N
化简得：
2L = (x + 1)C - N
对上述公式继续分析：由于偶数乘以任何数都为偶数，因此 2L 一定为偶数，则可推导出可能的情况：
• 情况1：偶数 = 偶数 - 偶数
• 情况2：偶数 = 奇数 - 奇数
由step1中（1）得出的结论，如果 N 是偶数，则第一圈快慢指针就相遇了。 由step1中（2）得出的结论，如果 N
是奇数，则fast指针和slow指针在第一轮的时候套圈了，开始进行下一轮的追逐；当 N 是奇数，要满足以上的公式，则 (x+1)C
必须也要为奇数，即 C 为奇数，满足（2）a中的结论，则快慢指针会相遇。 因此，step1中的 N 是奇数，C 是偶数
不成立，既然不存在该情况，则快指针一次走3步最终一定也可以相遇。 快指针一次走4、5……步最终也会相遇，其证明方式同上。
typedefstructListNode ListNode; bool hasCycle(structListNode* head){ ListNode* slow,* fast; slow = fast = head;while(fast && fast->next){ slow = slow->next;int n =3;//fast每次⾛三步while(n--){if(fast->next) fast = fast->next;elsereturn false;}if(slow == fast){return true;}}return false;}
环形链表II
题目链接↓
环形链表II
题目讲解↓
思路：快慢指针，在环里一定会相遇
相遇点到入环节点的距离 == 头结点到入环节点的距离
//IItypedefstructListNode ListNode;structListNode*detectCycle(structListNode* head){//创建快慢指针 ListNode* slow = head; ListNode* fast = head;while(fast && fast->next){ slow = slow->next; fast = fast->next->next;if(slow == fast){//相遇点---找入环节点（相遇点到入环节点的距离 == 头结点到入环节点的距离） ListNode* pcur = head;while(pcur != slow){ pcur = pcur->next; slow = slow->next;}return pcur;}}//链表不带环returnNULL;}
- 思考为什么相遇点到入环节点的距离 = = 头结点到入环节点的距离 思考为什么相遇点到入环节点的距离 == 头结点到入环节点的距离 思考为什么相遇点到入环节点的距离==头结点到入环节点的距离
说明:
H为链表的起始点，E为环入口点，M为判环时的相遇点
设:
环的长度为 R，H到E的距离为 L，E到M的距离为 X，则：M到E的距离为 R-X 在判环时，快慢指针相遇时所走的路径长度：
• fast：L + X + nR • slow：L + X 注意:当慢指针进入环时，快指针可能已经在环中绕了n圈了，n至少为1 因为：快指针先进环走到M的位置，最后又在M的位置与慢指针相遇慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针 因为：慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们之间的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的，而快指针速度是慢指针的两倍，因此有如下关系：
2 *(L+X) = L+X + nR
化简得：
L+X = nR
L = nR - X
进一步变形：
L = (n-1)R + (R-X)
（n为1,2,3,4,……，n的大小取决于环的大小，环越小n越大）
极端情况下，假设n=1，此时：
L = R - X
代码仓库
仓库地址
感谢大佬们三连，你的鼓励就是对我创作的激励！！！ \color{purple}{感谢大佬们三连，你的鼓励就是对我创作的激励！！！} 感谢大佬们三连，你的鼓励就是对我创作的激励！！！
