devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Leetcode刷题——单链表2_fast && fast->next

作者：笔触狂放9 | 2024-04-14 12:22:56

赞

踩

fast && fast->next

目录

练习题1 链表分割

练习题2 链表的回文结构 

练习题3 链表相交 

练习题4 判断是否为环形链表 

快慢指针延伸问题 

 练习题5 找环形链表的节点

 练习题6 复制带随机指针的链表

练习题1 链表分割

点击跳转

 思路：

将链表一分为2，以x为界限，大于x的尾插到新链表1，小于x的尾插到新链表2

，之后再将新链表1，头插到新链表2，跟归并排序有点像

  1. class Partition {
  2. public:
  3.     ListNode* partition(ListNode* pHead, int x) {
  4.           ListNode*Guard1=(ListNode*)malloc(sizeof(ListNode));
  5.          ListNode*Guard2=(ListNode*)malloc(sizeof(ListNode));
  6.          ListNode*tail1=Guard1;
  7.          ListNode*tail2=Guard2;
  8.         while(pHead)
  9.         {
  10.             if(pHead->val<x)
  11.             {
  12.                 tail1->next=pHead;
  13.              tail1=tail1->next;
  14.             }
  15.             else
  16.             {
  17.                 tail2->next=pHead;
  18.                 tail2=tail2->next;
  19.             }
  20.                  pHead=pHead->next;
  21.         }
  22.         tail1->next=Guard2->next;
  23.         tail2->next=NULL;
  24.         free(Guard2);
  25.         return Guard1->next;
  26.     }
  27. };

练习题2 链表的回文结构 

思路：

1.先找到中间节点 

2.从中间节点一直到末尾节点内的节点进行逆置

3. 用俩个节点分别指向头和中间位置，然后挨个进行数字比较，若不想等，直接退出

 注：当奇数时候，第一个2，仍然指向3，因此判断相等

  1. struct ListNode* middleNode(struct ListNode* head){
  2. struct ListNode*fast,*slow;
  3. fast=slow=head;
  4. while(fast&&fast->next)
  5. {
  6.     fast=fast->next->next;
  7.     slow=slow->next;
  8. }
  9. return slow;
  10. }
  11. struct ListNode* reverseList(struct ListNode* head){
  12.     struct ListNode*cur=head;
  13.     struct ListNode*prve=NULL;
  14.     while(cur)
  15.     {
  16.  
  17.         struct ListNode*t=cur->next;
  18.         cur->next=prve;
  19.         prve=cur;
  20.         cur=t;
  21.     }
  22.     return prve;
  23. }
  24. class PalindromeList {
  25. public:
  26.     bool chkPalindrome(ListNode* A) {
  27.         ListNode*mid=middleNode(A);
  28.         struct ListNode*rmid=reverseList(mid);
  29.         while(A&&rmid)
  30.         {
  31.             if(A->val!=rmid->val)
  32.                 return false;
  33.             else
  34.             {
  35.                 rmid=rmid->next;
  36.                 A=A->next;
  37.             }
  38.         }
  39.         return true;
  40.     }
  41. };

 方法二：临时拷贝一份，然后一个一个比较

练习题3 链表相交 

160. 相交链表 - 力扣（LeetCode）

 相交链表特点：最后一个节点的地址相等

 方法：1.求俩个出链表的长度，即让俩个链表都走到尾节点

            2.求出他们的距离差d

            3.较长的链表先走d步，然后俩个链表开始一起走，每次走一步

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode *newhead1=headA;
  3.   struct ListNode *newhead2=headB;
  4.   int k=1;int z=1;int c=0;
  5.   while(newhead1->next)
  6.   {
  7.       newhead1=newhead1->next;
  8.       k++;
  9.   }
  10.   while(newhead2->next)
  11.   {
  12.       newhead2=newhead2->next;
  13.       z++;
  14.   }
  15.   if(newhead1!=newhead2)
  16.   return NULL;
  17. c=abs(k-z);
  18. while(c--)
  19. {
  20.     if(k>z)
  21.    headA=headA->next;
  22.     else
  23.     headB=headB->next;
  24. }
  25. while(headA&&headB)
  26. {
  27.     if(headA==headB)
  28.     return headA;
  29.     else
  30.     {
  31.         headA=headA->next;
  32.         headB=headB->next;
  33.     }
  34. }
  35. return NULL;
  36. }
  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode *newhead1=headA;
  3.   struct ListNode *newhead2=headB;
  4.   int k=1;int z=1;
  5.   while(newhead1->next)
  6.   {
  7.       newhead1=newhead1->next;
  8.       k++;
  9.   }
  10.   while(newhead2->next)
  11.   {
  12.       newhead2=newhead2->next;
  13.       z++;
  14.   }
  15.   if(newhead1!=newhead2)
  16.   return NULL;
  17. int gap=abs(k-z);
  18.  struct ListNode *Longlist=headA;
  19.   struct ListNode *ShoreList=headB;
  20. if(k<z)
  21. {
  22.     Longlist=headB;
  23.     ShoreList=headA;
  24. }
  25. while(gap--)
  26. {
  27.     Longlist=Longlist->next;
  28. }
  29. while(Longlist!=ShoreList)
  30. {
  31.       Longlist=Longlist->next;
  32.       ShoreList=ShoreList->next;
  33. }
  34. return Longlist;
  35. }

练习题4 判断是否为环形链表 

141. 环形链表 - 力扣（LeetCode）

 带环链表：1.不能遍历，会陷入死循环

利用快慢指针，快指针一次走俩步，慢指针走一步

 当slow走到中间位置时，fast进入环内

当慢指针进环时，快指针在环内已经走了一小会了，具体走到了哪里，无法知晓 （要根据环的大小决定）,但是可以知道fast在环里走的路程，是slow从中间到进环路程的2倍

slow进入环后，看作是fast追赶slow

假设在红色位置fast追上了slow

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

快慢指针延伸问题 

 

 证明：slow走一步，fast走俩步，fast能追上slow

假设：slow进环以后，fast和slow之间的差距是N，即追赶距离为N

 slow和fast每移动一次，他们的距离会缩小一格

因此距离由：N,N-1,N-2,N-3……0

所以，能追上

证明：slow走一步，fast走三部，能否追得上

假设：slow进环以后，fast和slow之间的差距是N，即追赶距离为N

一开始fast在3，slow进入圆环

 slow和fast每移动一次，他们的距离会缩小2格，他们的距离N=9

 

此时距离是-1，-1意味着，他们之间的距离变成了C-1（C是环的长度）

最终距离是0还是其他数字，由N决定

如果N是奇数，N=9

9，7，5，3，1，-1

-1意味着，他们之间的距离变成了C-1（C是环的长度）

如果C-1是偶数，即他们的距离是偶数每次-2，一定追得上，如果C-1是奇数，又得去判断下一次C-1是偶数还是奇数

因此，能否追的上如果距离是偶数，则追得上

      如果距离是奇数，得看C-1是否为偶

 练习题5 找环形链表的节点

142. 环形链表 II - 力扣（LeetCode）

 方式1.公式证明

用快慢指针:fast走的距离=2*slow的距离

公式推导

假设进环前的长度L，假设环的长度C，入口点到相遇点距离x

 slow所走距离：L+X，慢指针所走的距离不可能超过一圈，因为N最大是C-1

fast所走距离：L+NC+X，N代表fast走过的圈数，N>=1

2（L+X）=L+X+NC

(L+X)=NC

L=NC-X

L=(N-1)*C+C-X

左边是A所走距离，右边是B所走距离

可证明：一个指针A从头开始走，另一个指针B从相遇点开始走，最终会在入口点相遇

  1. struct ListNode* detectCycle(struct ListNode* head) {
  2.     struct ListNode* slow = head;
  3.     struct ListNode* fast = head;
  4.     struct ListNode* meetnextl =NULL;
  5.     while (fast && fast->next)
  6.     {
  7.         slow = slow->next;
  8.         fast = fast->next->next;
  9.         if (fast == slow)
  10.         {
  11.             meetnextl = fast;
  12.          while(head!=meetnextl)
  13.          {
  14.              meetnextl=meetnextl->next;
  15.              head=head->next;
  16.          }
  17.          return head;
  18.         }
  19.     }
  20.    
  21.     return NULL;
  22. }

方法2：转换成相交问题

fast旁白的黑色是相遇点，下面蓝色是相遇点的下一个点，A和B链表的交点，就是入口点 ，

然后让长的先走，接着同时走，跟上面的题一样

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode *newhead1=headA;
  3.   struct ListNode *newhead2=headB;
  4.   int k=1;int z=1;
  5.   while(newhead1->next)
  6.   {
  7.       newhead1=newhead1->next;
  8.       k++;
  9.   }
  10.   while(newhead2->next)
  11.   {
  12.       newhead2=newhead2->next;
  13.       z++;
  14.   }
  15.   if(newhead1!=newhead2)
  16.   return NULL;
  17. int gap=abs(k-z);
  18.  struct ListNode *Longlist=headA;
  19.   struct ListNode *ShoreList=headB;
  20. if(k<z)
  21. {
  22.     Longlist=headB;
  23.     ShoreList=headA;
  24. }
  25. while(gap--)
  26. {
  27.     Longlist=Longlist->next;
  28. }
  29. while(Longlist!=ShoreList)
  30. {
  31.       Longlist=Longlist->next;
  32.       ShoreList=ShoreList->next;
  33. }
  34. return Longlist;
  35. }
  36.  struct ListNode *hasCycle(struct ListNode *head) {
  37.      struct ListNode *fast=head;
  38.      struct ListNode *slow=head;
  39.      while(fast&&fast->next)
  40.      {
  41.          fast=fast->next->next;
  42.          slow=slow->next;
  43.          if(slow==fast)
  44.          return slow;
  45.      }
  46.      return fast;
  47.     
  48. }
  49. struct ListNode* detectCycle(struct ListNode* head) {
  50.     struct ListNode* guard1 = hasCycle(head);
  51.     if(guard1==NULL)
  52.     return NULL;
  53.      struct ListNode*fast=head;
  54.       struct ListNode*slow=head;
  55.     struct ListNode* meetnextl =NULL;
  56.     while (fast && fast->next)
  57.     {
  58.         slow = slow->next;
  59.         fast = fast->next->next;
  60.       if (fast == slow)
  61.         {
  62.             meetnextl = fast->next;
  63.             fast->next=NULL;
  64.              struct ListNode* guard2 = getIntersectionNode(head, meetnextl);
  65.              return guard2;
  66.         }
  67.     }
  68.    
  69.     return NULL;
  70. }

 练习题6 复制带随机指针的链表

138. 复制带随机指针的链表 - 力扣（LeetCode）

 思路：

1.先拷贝各个节点，插到相对应的节点后面，然后将链表连接起来

 2.然后将cur的random所指指针赋值给copy的random

if(cur->random!=NULL)

copy->random=cur->random->next

3.将各节点拷贝下来进行链接，顺便链接原链表

  1. * struct Node {
  2.  *     int val;
  3.  *     struct Node *next;
  4.  *     struct Node *random;
  5.  * };
  6.  */
  8. struct Node* copyRandomList(struct Node* head) {
  9.     struct Node*cur=head;
  10.       struct Node* next=NULL;
  11.           struct Node*copy=NULL;
  12.     while(cur)
  13.     {
  14.         //1.拷贝一份插入链表内
  15.        copy=(struct Node*)malloc(sizeof( struct Node));
  16.       next=cur->next;
  17.       copy->val=cur->val;
  18.         cur->next=copy;
  19.         copy->next=next;
  20.         cur=next;
  21.     }
  22.     cur=head;
  23.  
  24. 	while(cur)
  25.     {   //2.链接random
  26.     copy=cur->next;
  27.     if(cur->random==NULL)
  28.    copy->random=NULL;
  29.    else
  30.         copy->random=cur->random->next;
  31.         cur=cur->next->next;
  32.     }
  33.     cur=head;
  34.     struct Node*newhead=NULL;
  35.     struct Node*tail=NULL;
  36.     while(cur)
  37.     {
  38.         copy=cur->next;
  39.         next=copy->next;
  40.         if(newhead==NULL)
  41.         newhead=tail=copy;
  42.         else
  43.         {
  44.             tail->next=copy;
  45.             tail=tail->next;
  46.         }
  47.         cur->next=next;
  48.         cur=next;
  49.     }
  50.     return newhead;
  51. }

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

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

  

闽ICP备14008679号