• Leetcode刷题——单链表2

    目录

    练习题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
    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
    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
    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.  */
    7.  
    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. }

  • 相关阅读:
    Linux项目自动化构建工具make/makefile
    Python之条件语句&逻辑运算符
    阿里笔试——北京阿里笔试题总结
    利用gpt进行数据分析：用户生命周期专题分析
    Spring Boot 日志文件
    大二Web课程设计：服装网页设计题材——HTML+CSS汉服文化带背景音乐素材带视频（12页）
    使用C#调用P6 Primavera WebService(自建服务IntegrationAPI)
    负数在计算机中的二进制表示方法
    C++ AVL树
    Windows运行多个Tomcat
  • 原文地址：https://blog.csdn.net/weixin_49449676/article/details/126105052