一、顺序表习题1.1 移除顺序表元素思路一查找val值对应的下标pos执行删除pos位置数据的操作但是时间复杂度是n^2for查找On及删除pos位置的数据On。思路二创建新数组空间大小与原数组一致遍历原数组将非val值放入tmp数组中再将tmp数组拷贝回原数组中以空间换时间时间复杂度On空间复杂度On。思路三双指针法定义两个变量src和dst1) nums[src]val,src,2) nums[src]!val,赋值(src-dst),dst,src。int removeElement(int* nums, int numsSize, int val) { //定义两个变量 int dst0,src0; while(srcnumsSize) { if(nums[src]!val) { nums[dst]nums[src]; dst; } src; } return dst; }1.2 删除有序数组中的重复项思路双指针法创建两个变量分别指向起始位置和下一个位置 1nums[src]nums[dst],src;2)nums[src]!nums[dst],dst,赋值(src给dst)srcint removeDuplicates(int* nums, int numsSize) { int dst0,srcdst1; while(srcnumsSize) { if(nums[src] ! nums[dst] dst!src) { nums[dst]nums[src]; } src; } return dst1; }1.3 合并两个有序数组思路一先合并再排序冒泡排序On^2思路二创建新数组空间大小和num1一致遍历两个原数组数据比较大小并放到tmp中时间复杂度On空间复杂度On思路三设置三个变量,从后往前比较大小找大。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int l1m-1; int l2n-1; int l3mn-1; while(l1 0 l2 0) { if(nums1[l1]nums2[l2]) { nums1[l3--]nums1[l1--]; } else { nums1[l3--]nums2[l2--]; } } while(l20) { nums1[l3--]nums2[l2--]; } }二、链表习题2.1 移除链表元素思路一遍历链表找值为val的结点执行删除指定位置的数据的操作while找所有值为val{找到了删除pos位置的结点}时间复杂度为On^2。思路二创建新链表遍历原链表将值不为val的结点拿下来尾插typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { //创建空链表 ListNode *newHead,*newTail; newHeadnewTailNULL; ListNode *pcurhead; while(pcur) { if(pcur-val!val) { //尾插 //链表为空 if(newHeadNULL) { newHeadnewTailpcur; } else { //链表非空 newTail-nextpcur; newTailnewTail-next; } } pcurpcur-next; } if(newTail) newTail-nextNULL; return newHead; }2.2 反转链表思路一:创建新链表遍历原链表每个结点头插到新链表中。思路二创建三个指针typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode *n1,*n2,*n3; if(headNULL) { return head; } n1NULL,n2head;n3n2-next; while(n2) { n2-nextn1; n1n2; n2n3; if(n3) { n3n3-next; } } return n1; }2.3 链表中间结点思路一求链表的总长度总长度除以2求中间结点的位置返回中间位置的结点时间复杂度为On。思路二快慢指针typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { ListNode* slowhead; ListNode* fasthead; while(fastfast-next) { slowslow-next; fastfast-next-next; } return slow; }2.4 合并两个有序链表思路一将结点放到指定位置之前思路二创建空链表typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1NULL) { return list2; } if(list2NULL) { return list1; } //创建空链表 ListNode *newHead,*newTail; newHeadnewTailNULL; ListNode *l1list1; ListNode *l2list2; while(l1 l2) { if(l1-vall2-val) { //l1尾插到新链表中 if(newHeadNULL) { //链表为空 newHeadnewTaill1; } else { //链表非空 newTail-nextl1; newTailnewTail-next; } l1l1-next; } else { //l2尾插到新链表中 if(newHeadNULL) { //链表为空 newHeadnewTaill2; } else { //链表非空 newTail-nextl2; newTailnewTail-next; } l2l2-next; } } //要么l1为空要么l2为空 if(l2) { newTail-nextl2; } if(l1) { newTail-nextl1; } return newHead; }2.5 链表分割思路创建两个链表小链表、大链表遍历原链表小的尾插到小链表中大的尾插到大链表中大链表和小链表首尾相连。class Partition { public: ListNode* partition(ListNode* pHead, int x) { //创建两个带头的空链表 ListNode *lessHead,*lessTail; lessHeadlessTail(ListNode*)malloc(sizeof(ListNode)); ListNode *greatHead,*greatTail; greatHeadgreatTail(ListNode*)malloc(sizeof(ListNode)); ListNode *pcurpHead; //比较大小 while(pcur) { if(pcur-valx) { //比x值小的尾插到小链表 lessTail-nextpcur; lessTaillessTail-next; } else { //比x值大的尾插到大链表 greatTail-nextpcur; greatTailgreatTail-next; } pcurpcur-next; } //将大链表的尾结点置为空 greatTail-nextNULL; //连接两个链表 lessTail-nextgreatHead-next; ListNode *retlessHead-next; free(lessHead); free(greatHead); return ret; } };2.6 链表的回文结构思路找链表的中间结点快慢指针将中间结点作为新的链表的头结点进行反转链表class PalindromeList { public: ListNode* middleNode(ListNode *head) { ListNode *slow,*fast; slowfasthead; while(fast fast-next) { slowslow-next; fastfast-next-next; } return slow; } ListNode* reverseList(ListNode *head) { if(headNULL) { return head; } ListNode *n1,*n2,*n3; n1NULL,n2head,n3n2-next; while(n2) { n2-nextn1; n1n2; n2n3; if(n3) { n3n3-next; } } return n1; } bool chkPalindrome(ListNode* A) { ListNode *midmiddleNode(A); ListNode *rightreverseList(mid); ListNode *leftA; while(right) { if(left-val!right-val) { return false; } leftleft-next; rightright-next; } return true; } };2.7 相交链表思路求两个链表的长度并计算长度差长链表先走长度差步然后两个链表同时往后遍历。typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //计算两个链表的长度 ListNode *paheadA; ListNode *pbheadB; int sizeA0;int sizeB0; while(pa) { sizeA; papa-next; } while(pb) { sizeB; pbpb-next; } //计算长度差 int gapabs(sizeA-sizeB); ListNode *shortListheadA; ListNode *longListheadB; if(sizeAsizeB) { longListheadA; shortListheadB; } //让longList先走gap步 while(gap--) { longListlongList-next; } //longList shortList在同一起跑线 while(shortList) { if(shortListlongList) { return longList; } shortListshortList-next; longListlongList-next; } return NULL; }2.8 环形链表1思路快慢指针在环里追逐若链表带环快慢指针一定会相遇。typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode* fasthead; ListNode* slowhead; while(fastfast-next) { slowslow-next; fastfast-next-next; if(slowfast) { return true; } } return false; }2.9 环形链表2快慢指针相遇点和头结点到入环起始结点的距离是相等的。typedef struct ListNode ListNode; struct ListNode *detectCycle(struct ListNode *head) { ListNode *slowhead; ListNode *fasthead; while(fastfast-next) { slowslow-next; fastfast-next-next; if(slowfast) { //找相遇点 //相遇点和头结点入环第一个结点的距离相等 ListNode *pcurhead; while(pcur!slow) { pcurpcur-next; slowslow-next; } return pcur; } } return NULL; }2.10 随机链表的复制typedef struct Node Node; Node* buyNode(int x) { Node *newnode (Node*)malloc(sizeof(Node)); newnode-valx; newnode-nextnewnode-randomNULL; return newnode; } void AddNode(Node *head) { Node* pcurhead; while(pcur) { Node* newnodebuyNode(pcur-val); Node* next pcur-next; newnode-nextnext; pcur-nextnewnode; pcurnext; } } void SetRandom(Node *head) { Node* pcurhead; while(pcur) { Node* copypcur-next; if(pcur-random) { copy-randompcur-random-next; } pcurcopy-next; } } struct Node* copyRandomList(struct Node* head) { if(headNULL) { return head; } //在原链表基础上拷贝结点并插入在原链表中 AddNode(head); //设置random SetRandom(head); //断开新链表 Node* pcurhead; Node* copyHead,*copyTail; copyHeadcopyTailpcur-next; while(copyTail-next) { pcurcopyTail-next; copyTail-nextpcur-next; copyTailcopyTail-next; } return copyHead; }