devbox
小桥流水78
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

顺序表、链表相关OJ题（2）_中级oj算法题

作者：小桥流水78 | 2024-06-26 08:41:30

赞

踩

中级oj算法题

创作不易，友友们给个三连吧！！

一、旋转数组（力扣）

经典算法OJ题：旋转数组

思路1：每次挪动1位，右旋k次

时间复杂度：o(N^2)       

右旋最好情况：k是n的倍数，相当于不右旋，此时为o（1）

右旋最坏情况：k%n==n-1,此时为o（N^2）

空间复杂度:o(1)

  1. void rotate(int* nums, int numsSize, int k) 
  2. {
  3.     k%=numsSize;
  4.     while(k)
  5.     {
  6.         int temp=nums[numsSize-1];
  7.         //从后往前挪 
  8.         for(int i=numsSize-1;i>0;i--)
  9.         {
  10.              nums[i]=nums[i-1];//最后一个是nums[1]=num[0]
  11.         }
  12.         nums[0]=temp;
  13.         k--;//旋转一次就减一次
  14.     }
  15. }

注：这是常规思路，但是由于空间复杂度太高，数组个数特别多的时候，在力扣运行的时候超出了时间限制！

思路2：创建一个和nums一样长度的新数组，将nums数组的后k个元素，先按顺序放进新数组里，然后剩下前面的n-k个元素，再按顺序放进新数组,最后再将新数组的数据拷贝到nums中

时间复杂度：o(N)

空间复杂度：o(N)

  1. void rotate(int* nums, int numsSize, int k) 
  2. {
  3.    k%=numsSize;
  4.    int arr[numsSize];//vs不支持变长数组，但是牛客支持，如果是vs只能使用动态数组。
  5.    memcpy(arr,nums+numsSize-k,sizeof(int)*k);//nums的后k个按顺序拷贝到新数组的前面
  6.    memcpy(arr+k,nums,sizeof(int)*(numsSize-k));//nums的前n-k个按顺序拷贝到新数组的后面
  7.    memcpy(nums,arr,sizeof(int)*numsSize);//新数组完全拷贝到nums数组中
  8. }

思路3：前n-k个元素逆置，后k个元素逆置，再整体逆置

时间复杂度：o(N)

空间复杂度：o(1)

  1. void reverse (int *arr,int left,int right)//实现逆序函数
  2. {
  3.     int temp=0;
  4.     while(left<right)
  5.     {
  6.         temp=arr[left];
  7.         arr[left]=arr[right];
  8.         arr[right]=temp;
  9.         left++;
  10.         right--;
  11.     }
  12. }
  13. void rotate(int* nums, int numsSize, int k) 
  14. {
  15.     k%=numsSize;
  16.    reverse(nums,0,numsSize-k-1);//前n-k个元素逆序
  17.    reverse(nums,numsSize-k,numsSize-1);//后k个逆序
  18.    reverse(nums,0,numsSize-1);//完全逆序
  19. }

二、消失的数字（力扣）

经典算法OJ题：消失的数字

思路1：先进行排序，如果后一个不等于前一个+1，就可以找到消失的数据，但是目前掌握的排序中，冒泡排序的时间复杂度是o（N^2），而qsort的时间复杂度是o（logN+N）,均不符合题意，这里不做考虑！

思路2：让0和0-numsSize的所有数都异或一遍，再和数组中的所有元素异或一边，最后得到的结果就是消失的数（利用了a^a=0，a^0=a的结论）

时间复杂度：o(N)

空间复杂度：o(1)

  1. int missingNumber(int* nums, int numsSize)
  2. {
  3. int x=0;
  4. for(int i=0;i<numsSize;i++)
  5. {
  6.     x^=i;
  7.     x^=nums[i];
  8. }
  9. x^=numsSize;//还多了一个数
  10. return x;
  11. }

思路3：0-numsSize的所有数相加，然后减去数组中的所有元素之和，得到的就是消失的数字。

时间复杂度：o(N)

空间复杂度：o(1)

  1. int missingNumber(int* nums, int numsSize)
  2. {
  3.     int sum=0;//记录
  4. for(int i=0;i<numsSize;i++)
  5. {
  6.   sum+=i;
  7.   sum-=nums[i];
  8. }
  9. sum+=numsSize;
  10. return sum;
  11. }

三、链表中倒数第k个结点（牛客）

经典算法OJ题：链表中倒数第k个结点

思路1：第一次循环计算结点的个数count，然后求倒数第k个就是正数的第count-k个结点

空间复杂度:o(N)

时间复杂度:o(1)

  1.  typedef struct ListNode ListNode;
  2. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
  3.  {
  4. ListNode* pcur= pListHead;
  5. int count=0;//统计结点
  6. while(pcur)
  7. {
  8.     pcur=pcur->next;
  9.     count++;
  10. }
  11. if(count<k)
  12. return NULL;//考虑链表为NULL，以及k大于链表结点数
  13. pcur= pListHead;
  14. for(int i=0;i<count-k;i++)
  15. pcur=pcur->next;
  16. return pcur;
  17. }

思路2：（快慢指针）fast指针先走k步，然后fast和slow同时走，始终保持k的距离，当fast走到NULL的时候，slow对应的恰好就是倒数第k个结点

空间复杂度:o(N)

时间复杂度:o(1)

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
  2.  {
  3. struct ListNode*fast=pListHead,*slow=pListHead;
  4. while(k)
  5. {
  6.     //考虑k大于结点数的情况，此时链表很早就为空了
  7.     if(fast==NULL)
  8.     return NULL;
  9.     fast=fast->next;
  10.     k--;
  11. }
  12. //同时走，直到fast为NULL，此时slow指向倒数第k个结点
  13. while(fast)
  14. {
  15.     fast=fast->next;
  16.     slow=slow->next;
  17. }
  18. //如果k<=0.那么第一个while循环不会进入，
  19. //fast和slow同时走，最后都会指向空，所以不需要额外判断
  20. return slow;
  21. }

思路3：直接反转链表，然后直接找第k个结点

该方法直接改变了链表结构，使得phead变成了一个尾结点，与其他结点建立不起联系，所以该思路不行（尽量不要去改变原先链表的结构）在力扣中过不了。

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
  2.  {
  3. //直接反转链表，然后找第k个结点
  4. if(pListHead==NULL)
  5. return NULL;
  6. struct ListNode*p1=NULL;
  7. struct ListNode*p2=pListHead;
  8. struct ListNode*p3=pListHead->next;
  9. int count=0;//用来数数
  10. while(p2)
  11. {
  12.     p2->next=p1;
  13.     p1=p2;
  14.     p2=p3;
  15.     if(p3)
  16.     p3=p3->next;
  17.     ++count;
  18. }
  19. //此时的p1就是新链表的头结点
  20. if(k<=count||k>count)
  21. return NULL;
  22. while(--k)
  23. {
  24. p1=p1->next;
  25. }
  26. return p1;
  27. }

四、相交链表（力扣）

经典算法OJ题：相交链表

思路1：A链表逐个结点与B链表比较，如果存在相等，则就是相交结点（注：要比较指针而不能比较值，因为值是可以重复的）

空间复杂度:o(N^2)

时间复杂度:o(1)

  1. typedef struct ListNode ListNode;
  2. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  3. {
  4.    ListNode* pcurA=headA;
  5.    ListNode* pcurB=headB;
  6.    while(pcurA)
  7.    {
  8.        while(pcurB)
  9.        {
  10.            if(pcurA==pcurB)
  11.            return pcurA;
  12.            pcurB=pcurB->next;
  13.        }
  14.        pcurB=headB;
  15.        pcurA=pcurA->next;
  16.    }
  17.    return NULL;
  18. }

思路2：长的链表往后走长度差，再同时走，直到相等就是相交点

空间复杂度:o(N)

时间复杂度:o(1)

  1. typedef struct ListNode ListNode;
  2. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  3. {
  4.    ListNode * Apcur=headA;//用来遍历A链表
  5.     ListNode * Bpcur=headB;//用来遍历A链表
  6.     int a=0;//数a长度
  7.     int b=0;//数b长度
  8. while(Apcur)
  9. {
  10. Apcur=Apcur->next;
  11. a++;
  12. }
  13. while(Bpcur)
  14. {
  15. Bpcur=Bpcur->next;
  16. b++;
  17. }
  18. //找最小数，写俩while循环，只要大的数才可以走，小的走不了
  19. int m=a>b?b:a;
  20. while(a-m)
  21. {
  22.     headA=headA->next;
  23.     a--;
  24. }
  25. while(b-m)
  26. {
  27.     headB=headB->next;
  28.     b--;
  29. }
  30. while(headA)
  31. {
  32.     if(headA==headB)
  33.     return headA;
  34.     headA=headA->next;
  35.     headB=headB->next;
  36. }
  37. return NULL;
  38. }

五、链表的回文结构（牛客）

经典算法OJ题：链表的回文结构

思路1：找到中间结点，然后逆置后半段,然后将后续半段和前半段的链表同时走，如果其中一个走到空了值依旧是相等的，那么就是回文结构！！

空间复杂度:o(N)

时间复杂度:o(1)

  1. ListNode *middleNode(struct ListNode *phead)
  2. {
  3. struct ListNode *fast,*slow;
  4. fast=slow=phead;
  5. while(fast!=NULL&&fast->next!=NULL)
  6. {
  7. fast=fast->next->next;
  8. slow=slow->next;
  9. }
  10. return slow;
  11. }
  12. struct ListNode* reverseList(struct ListNode* head)
  13. {
  14.     //链表为空的时候
  15.     if(head==NULL)
  16.     return head;
  17.     //链表不为空的时候，创建3个指针，分别指向前驱、当前、后继结点
  18. struct ListNode*p1,*p2,*p3;
  19. p1=NULL;//前驱
  20. p2=head;//当前
  21. p3=head->next;//后继
  22. while(p2)
  23. {
  24.     //改变指向
  25. p2->next=p1;
  26. //向后挪动
  27. p1=p2;
  28. p2=p3;
  29. //考虑p3为NULL的时候
  30. if(p3)
  31. p3=p3->next;
  32. }
  33. return p1;
  34. }
  35. class PalindromeList {
  36. public:
  37.     bool chkPalindrome(ListNode* A) 
  38.     {
  39.         struct ListNode *mid=middleNode(A);//找中间结点
  40.            struct ListNode *rmid=reverseList(mid);//逆序后半段
  41.            while(rmid)
  42.            {
  43.             if(A->val!=rmid->val)
  44.             return false;
  45.             A=A->next;
  46.             rmid=rmid->next;
  47.            }
  48.            return true;
  49.     }
  50. };

六、随机链表的复制（力扣）

经典算法OJ题：随机链表的复制

思路1：1、插入拷贝结点到原结点的后面，2、控制拷贝结点的random，3、拷贝结点解下来，尾插到新链表上，同时恢复原链表

空间复杂度:o(N)

时间复杂度:o(N)

  1. typedef struct Node Node;
  2. Node* copyRandomList(Node* head) 
  3. {
  4.     if(head==NULL)
  5.     return NULL;
  6. 	//将拷贝结点放在原结点的后面
  7.       Node*pcur=head;
  8.     while(pcur)
  9.     {
  10.        Node*copy=(Node*)malloc(sizeof(Node));//拷贝结点
  11.        copy->val=pcur->val;
  12.        //插入
  13.        copy->next=pcur->next;
  14.        pcur->next=copy;
  15.        
  16.        //迭代
  17.        pcur=pcur->next->next;
  18.     }
  19.     //控制拷贝结点的random指针
  20.     pcur=head;
  21.     while(pcur)
  22.     {
  23.         //有可能random指向NULL
  24.         Node* copy=pcur->next;
  25.         if(pcur->random==NULL)
  26.         copy->random=NULL;
  27.         else
  28.         //拷贝结点的random恰好在原结点的random后面
  29.         copy->random=pcur->random->next;
  30.         //迭代
  31.         pcur=pcur->next->next;
  32.     }
  33.     //将拷贝结点解下来尾插到新链表上
  34.     pcur=head;
  35.     Node*newhead,*newtail,*temp;
  36.     newhead=newtail=(struct Node*)malloc(sizeof(struct Node));
  37.     temp=NULL;//用来记录遍历点
  38.     while(pcur)
  39.     {
  40.         Node* copy=pcur->next;
  41.         temp=copy->next;//记录遍历点
  42.         newtail->next=copy;//尾插
  43.         newtail=newtail->next;
  44.      //修复原链表
  45.      pcur->next=temp;
  46.      //继续遍历
  47.      pcur=pcur->next;
  48.     }
  49.     Node*ret=newhead->next;//销毁哨兵结点前记住头结点
  50.     free(newhead);
  51.     newhead=NULL;
  52.     return ret;
  53. }

思路2：暴力拷贝链表，然后看原结点的random是原链表的第几个结点，对应的就是拷贝链表的的第几个结点

空间复杂度:o(N^2)

时间复杂度:o(N)

  1. typedef struct Node Node;
  2. Node* copyRandomList(Node* head) 
  3. {
  4.     if(head==NULL)
  5.     return NULL;
  6.     Node*pcur=head;
  7.     Node*newhead,*newtail;
  8.     newhead=newtail=(Node*)malloc(sizeof(Node));//哨兵结点
  9.    while(pcur)
  10.    {
  11.       Node*newnode=(Node*)malloc(sizeof(Node));
  12.       newnode->val=pcur->val;
  13.       newtail->next=newnode;
  14.       newtail=newnode;
  15.       //迭代
  16.       pcur=pcur->next;
  17.    }
  18.    newtail->next=NULL;//要记住最后有个NULL；
  19.    pcur=head;//回到链表头
  20.    Node*newpcur=newhead->next;//用来遍历新链表头
  21.    while(pcur)
  22.    {
  23.        int s=0;//记录节点与head的距离
  24.        Node*flag=head,*temp=pcur->random;//temp记住random结点
  25.        while(flag!=temp)
  26.        {
  27.            ++s;
  28.            flag=flag->next;
  29.        }
  30.        flag=newhead->next;//回到新链表的头
  31.        while(s--)
  32.        flag=flag->next;
  33.        //找到了，就接上
  34.       newpcur->random=flag;
  35.       pcur=pcur->next;
  36.       newpcur=newpcur->next;
  37.    }
  38.    Node*ret=newhead->next;
  39.    free(newhead);
  40.    newhead=NULL;
  41.    return ret;
  42. }

七、带环链表的快慢指针追击问题（力扣）

7.1 判断链表中是否有环

经典算法OJ题：判断链表是否带环

思路：快慢指针追击

  1.  typedef struct ListNode ListNode;
  2. bool hasCycle(struct ListNode *head)
  3. {
  4.     ListNode*fast,*slow;
  5.     fast=slow=head;
  6.     while(fast&&fast->next)
  7.     {
  8.         slow=slow->next;
  9.         fast=fast->next->next;
  10.         if(slow==fast)
  11.         return true;
  12.     }
  13.     return false;
  14. }

7.2 返回链表开始入环的第一个结点

思路1：利用相遇点到入口点距离等于链表头到入口点距离的结论

  1.  typedef struct ListNode ListNode;
  2. struct ListNode *detectCycle(struct ListNode *head)
  3. {
  4.     ListNode*fast,*slow;
  5.     fast=slow=head;
  6.     while(fast&&fast->next)
  7.     {
  8.         slow=slow->next;
  9.         fast=fast->next->next;
  10.         //相等，说明相遇了，链表带环
  11.         if(slow==fast)
  12.     {
  13.         ListNode*meet=slow;
  14.         while(meet!=head)
  15.         {
  16.             meet=meet->next;
  17.             head=head->next;
  18.         }
  19.         return meet;
  20.     }
  21.   }  
  22.   return NULL;
  23. }

思路2:在相遇点将带环链表拆开，转化成求链表相交结点的问题

  1. typedef struct ListNode ListNode;
  2.  struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
  3. {
  4.    ListNode * Apcur=headA;//用来遍历A链表
  5.     ListNode * Bpcur=headB;//用来遍历A链表
  6.     int a=0;//数a长度
  7.     int b=0;//数b长度
  8. while(Apcur)
  9. {
  10. Apcur=Apcur->next;
  11. a++;
  12. }
  13. while(Bpcur)
  14. {
  15. Bpcur=Bpcur->next;
  16. b++;
  17. }
  18. //找最小数，写俩while循环，只要大的数才可以走，小的走不了
  19. int m=a>b?b:a;
  20. while(a-m)
  21. {
  22.     headA=headA->next;
  23.     a--;
  24. }
  25. while(b-m)
  26. {
  27.     headB=headB->next;
  28.     b--;
  29. }
  30. while(headA)
  31. {
  32.     if(headA==headB)
  33.     return headA;
  34.     headA=headA->next;
  35.     headB=headB->next;
  36. }
  37. return NULL;
  38. }
  39. struct ListNode *detectCycle(struct ListNode *head)
  40. {
  41.     ListNode*fast,*slow;
  42.     fast=slow=head;
  43.     while(fast&&fast->next)
  44.     {
  45.         slow=slow->next;
  46.         fast=fast->next->next;
  47.         if(slow==fast)
  48.         {
  49.             //将带环链表的环拆开
  50.         ListNode*newhead=slow->next;
  51.         slow->next=NULL;
  52.         return getIntersectionNode(newhead,head);
  53.         }
  54.     }
  55.     return NULL;
  56. }

7.3 追击问题扩展

根据前两题可以知道对于带环的链表，fast走2步，slow走1步

1、必然会相遇，不会错过

2、L=（n-1）*C+（C-x）   一个指针从相遇点走，一个指针从链表头走，最后会在入口点相遇

如果fast走3步，slow走1步，可以得到什么结论？？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/758791
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号