ToB企服应用市场:ToB评测及商务社交产业平台

标题: 链表OJ题 [打印本页]
作者: 慢吞云雾缓吐愁    时间: 2024-6-15 03:58
标题: 链表OJ题
1. 链表的回文布局


由于单链表不能从后往前找节点，以是我们先找到中间节点，然后逆置，最后进行比力。
  1. #include <stdio.h>
  2. #include <stdbool.h>
  4. typedef struct ListNode
  5. {
  6.         int val;
  7.         struct ListNode* next;
  8. }ListNode;
  10. struct ListNode* middleNode(struct ListNode* head)
  11. {
  12.         ListNode* slow, * fast;
  13.         slow = fast = head;
  15.         while (fast && fast->next)
  16.         {
  17.                 slow = slow->next;
  18.                 fast = fast->next->next;
  19.         }
  21.         return slow;
  22. }
  24. struct ListNode* reverseList(struct ListNode* head)
  25. {
  26.         if (NULL == head)
  27.         {
  28.                 return head;
  29.         }
  31.         ListNode* n1, * n2, * n3;
  32.         n1 = NULL, n2 = head, n3 = head->next;
  34.         while (n2)
  35.         {
  36.                 n2->next = n1;
  37.                 n1 = n2;
  38.                 n2 = n3;
  40.                 if (n3)
  41.                 {
  42.                         n3 = n3->next;
  43.                 }
  44.         }
  46.         return n1;
  47. }
  49. bool chkPalindrome(ListNode* A)
  50. {
  51.         ListNode* mid = middleNode(A);
  52.         ListNode* rmid = reverseList(mid);
  54.         while (A && rmid)
  55.         {
  56.                 if (A->val != rmid->val)
  57.                 {
  58.                         return false;
  59.                 }
  61.                 A = A->next;
  62.                 rmid = rmid->next;
  63.         }
  65.         return true;
  66. }
复制代码
2. 相交链表


  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. struct ListNode
  5. {
  6.         int val;
  7.         struct ListNode* next;
  8. };
  10. struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
  11. {
  12.         struct ListNode* curA = headA;
  13.         struct ListNode* curB = headB;
  15.         int lenA = 0;
  17.         while (curA->next)
  18.         {
  19.                 ++lenA;
  20.                 curA = curA->next;
  21.         }
  22.        
  23.         int lenB = 0;
  25.         while (curB->next)
  26.         {
  27.                 ++lenB;
  28.                 curB = curB->next;
  29.         }
  31.         //不相交
  32.         if (curA != curB)
  33.         {
  34.                 return NULL;
  35.         }
  37.         int gap = abs(lenA - lenB);
  38.         //因为我们不知道A长还是B长，所以我们要用假设法，先假设A长，如果不对，再调换一下就行
  39.         struct ListNode* longList = headA;
  40.         struct ListNode* shortList = headB;
  42.         if (lenB > lenA)
  43.         {
  44.                 longList = headB;
  45.                 shortList = headA;
  46.         }
  48.         //让长的先走gap步
  49.         while (gap--)
  50.         {
  51.                 longList = longList->next;
  52.         }
  54.         //再同时走，找交点
  55.         while (longList != shortList)
  56.         {
  57.                 longList = longList->next;
  58.                 shortList = shortList->next;
  59.         }
  61.         return longList;
  62. }
复制代码
3. 链表中倒数第k个结点


思路2：
  1. #include <stdio.h>
  3. struct ListNode
  4. {
  5.         int val;
  6.         struct ListNoe* next;
  7. };
  9. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
  10. {
  11.         struct ListNode* slow = pListHead, * fast = pListHead;
  13.         //fast先走k步
  14.         while (k--)
  15.         {
  16.                 //k还没有减到0，链表已经空了，说明k大于链表的长度
  17.                 if (NULL == fast)
  18.                 {
  19.                         return NULL;
  20.                 }
  22.                 fast = fast->next;
  23.         }
  25.         //slow和fast同时走，fast走到空，slow就是倒数第k个
  26.         while (fast)
  27.         {
  28.                 slow = slow->next;
  29.                 fast = fast->next;
  30.         }
  32.         return slow;
  33. }
复制代码
4. 环形链表



  1. #include <stdbool.h>
  3. struct ListNode
  4. {
  5.         int val;
  6.         struct ListNode* next;
  7. };
  10. bool hasCycle(struct ListNode* head)
  11. {
  12.         struct ListNode* slow = head, * fast = head;
  14.         while (fast && fast->next)
  15.         {
  16.                 slow = slow->next;
  17.                 fast = fast->next->next;
  19.                 if (slow == fast)
  20.                 {
  21.                         return true;
  22.                 }
  23.         }
  25.         return false;
  26. }
复制代码
5. 环形链表 II

找入环点：

法一：
  1. #include <stdio.h>
  3. struct ListNode
  4. {
  5.         int val;
  6.         struct ListNode* next;
  7. };
  9. struct ListNode* detectCycle(struct ListNode* head)
  10. {
  11.         struct ListNode* slow = head, * fast = head;
  13.         while (fast && fast->next)
  14.         {
  15.                 slow = slow->next;
  16.                 fast = fast->next->next;
  18.                 if (slow == fast)
  19.                 {
  20.                         struct ListNode* meet = slow;
  22.                         while (meet != head)
  23.                         {
  24.                                 meet = meet->next;
  25.                                 head = head->next;
  26.                         }
  28.                         return meet;
  29.                 }
  30.         }
  32.         return NULL;
  33. }
复制代码
法二：
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. struct ListNode
  5. {
  6.         int val;
  7.         struct ListNode* next;
  8. };
  10. struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
  11. {
  12.         struct ListNode* curA = headA;
  13.         struct ListNode* curB = headB;
  15.         int lenA = 0;
  17.         while (curA->next)
  18.         {
  19.                 ++lenA;
  20.                 curA = curA->next;
  21.         }
  23.         int lenB = 0;
  25.         while (curB->next)
  26.         {
  27.                 ++lenB;
  28.                 curB = curB->next;
  29.         }
  31.         //不相交
  32.         if (curA != curB)
  33.         {
  34.                 return NULL;
  35.         }
  37.         int gap = abs(lenA - lenB);
  38.         struct ListNode* longList = headA;
  39.         struct ListNode* shortList = headB;
  41.         if (lenB > lenA)
  42.         {
  43.                 longList = headB;
  44.                 shortList = headA;
  45.         }
  47.         //让长的先走gap步
  48.         while (gap--)
  49.         {
  50.                 longList = longList->next;
  51.         }
  53.         //再同时走，找交点
  54.         while (longList != shortList)
  55.         {
  56.                 longList = longList->next;
  57.                 shortList = shortList->next;
  58.         }
  60.         return longList;
  61. }
  63. struct ListNode* detectCycle(struct ListNode* head)
  64. {
  65.         struct ListNode* slow = head, * fast = head;
  67.         while (fast && fast->next)
  68.         {
  69.                 slow = slow->next;
  70.                 fast = fast->next->next;
  72.                 if (slow == fast)
  73.                 {
  74.                         struct ListNode* meet = slow;
  75.                         struct ListNode* headx = meet->next;
  76.                         meet->next = NULL;
  78.                         return getIntersectionNode(head, headx);
  79.                 }
  80.         }
  82.         return NULL;
  83. }
复制代码
6. 随机链表的复制


写代码的时候建议一边画细图，一边写：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. struct Node
  5. {
  6.     int val;
  7.     struct Node *next;
  8.     struct Node *random;
  9. };
  11. struct Node* copyRandomList(struct Node* head)
  12. {
  13.     struct Node* cur = head;
  15.     //拷贝节点插入原节点的后面
  17.     while (cur)
  18.     {
  19.         struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
  20.         copy->val = cur->val;
  22.         //插入
  23.         copy->next = cur->next;
  24.         cur->next = copy;
  26.         //迭代
  27.         cur = cur->next->next;
  28.     }
  30.     //控制拷贝节点的random
  31.     cur = head;
  33.     while (cur)
  34.     {
  35.         struct Node* copy = cur->next;
  36.         
  37.         if (NULL == cur->random)
  38.         {
  39.             copy->random = NULL;
  40.         }
  41.         else
  42.         {
  43.             copy->random = cur->random->next;
  44.         }
  46.         //迭代
  47.         cur = cur->next->next;
  48.     }
  50.     //把copy节点解下来，链接成新链表
  51.     struct Node* copyhead = NULL, * tail = NULL;
  52.     cur = head;
  54.     while (cur)
  55.     {
  56.         struct Node* copy = cur->next;
  57.         struct Node* next = copy->next;
  59.         //尾插
  60.         if (NULL == tail)
  61.         {
  62.             copyhead = tail = copy;
  63.         }
  64.         else
  65.         {
  66.             tail->next = copy;
  67.             tail = tail->next;
  68.         }
  70.         cur->next = next;
  71.         cur = next;
  72.     }
  74.     return copyhead;
  75. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4