深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构刷题集】链表经典习题

2023-04-15

next cur head
😽PREFACE🎁欢迎各位→点赞👍+收藏⭐+评论📝📢系列专栏：数据结构刷题集🔊本专栏涉及到题目是数据结构专栏的补充与应用，只更新相关题目，旨在帮助提高代码熟练度💪种一棵树最好是十年前其次是现在移除链表元素题目链接：https://leetcode.cn/problems/remove-
😽 PREFACE
🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝
📢系列专栏： 数据结构刷题集
🔊本专栏涉及到题目是数据结构专栏的补充与应用，只更新相关题目，旨在帮助提高代码熟练度
💪 种一棵树最好是十年前其次是现在

移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

  1. struct ListNode* removeElements(struct ListNode* head, int val){
  2.     struct ListNode* prev=NULL,*cur=head;
  3.     while(cur)
  4.     {
  5.         if(cur->val==val)
  6.         {
  7.             prev->next=cur->next;
  8.             free(cur);
  9.             cur=prev->next;
  10.         }
  11.         else
  12.         {
  13.             prev=cur;
  14.             cur=cur->next;
  15.         }
  16.     }
  17.     return head;
  18. }

提交一下，我们会发现执行出错。

正确代码：

  1. struct ListNode* removeElements(struct ListNode* head, int val){
  2.     struct ListNode* prev=NULL,*cur=head;
  3.     while(cur)
  4.     {
  5.         if(cur->val==val)
  6.         {
  7.             if(cur==head)
  8.             {
  9.                 //头删
  10.                 head=cur->next;
  11.                 free(cur);
  12.                 cur=head;
  13.             }
  14.             else
  15.             {
  16.                 prev->next=cur->next;
  17.                 free(cur);
  18.                 cur=prev->next;
  19.             }  
  20.         }
  21.         else
  22.         {
  23.             prev=cur;
  24.             cur=cur->next;
  25.         }
  26.     }
  27.     return head;
  28. }

链表的中间结点

题目链接：https://leetcode.cn/problems/middle-of-the-linked-list/description/

正确代码：

  1. //尺取法
  2. struct ListNode* middleNode(struct ListNode* head){
  3.     struct ListNode* slow=head,*fast=head;
  4.     while(fast&&fast->next)
  5.     {
  6.         slow=slow->next;
  7.         fast=fast->next->next;
  8.     }
  9.     return slow;
  10. }

链表中倒数第k个结点

题目链接：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
  2.     struct ListNode* fast=pListHead,*slow=pListHead;
  3.     while(k--)
  4.     {
  5.         fast=fast->next;
  6.     }
  7.     while(fast)
  8.     {
  9.         slow=slow->next;
  10.         fast=fast->next;
  11.     }
  12.     return  slow;;
  13. }

结果代码运行不过：

正确代码：

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
  2.     struct ListNode* fast=pListHead,*slow=pListHead;
  3.     while(k--)
  4.     {
  5.         if(fast==NULL)//防止越界
  6.         {
  7.             return NULL;
  8.         }
  9.         fast=fast->next;
  10.     }
  11.     while(fast)
  12.     {
  13.         slow=slow->next;
  14.         fast=fast->next;
  15.     }
  16.     return  slow;;
  17. }

反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/

法一：画图+迭代

  1. //画图+迭代
  2. struct ListNode* reverseList(struct ListNode* head){
  3.     struct ListNode* prev,*cur,*next;
  4.     prev=NULL,cur=head,next=head->next;
  5.     while(cur)
  6.     {
  7.         //反转
  8.         cur->next=prev;
  9.         //迭代
  10.         prev=cur;
  11.         cur=next;
  12.         next=next->next;
  13.     }
  14.     return prev;
  15. }

这个只是最基本的逻辑，一运行发现还是过不了

  1. //画图+迭代
  2. struct ListNode* reverseList(struct ListNode* head){
  3.     struct ListNode* prev,*cur,*next;
  4.     prev=NULL,cur=head,next=head->next;
  5.     while(cur)
  6.     {
  7.         //反转
  8.         cur->next=prev;
  9.         //迭代
  10.         prev=cur;
  11.         cur=next;
  12.         if(next)
  13.             next=next->next;
  14.     }
  15.     return prev;
  16. }

再次提交，发现还是过不去：

正确代码1：

  1. //画图+迭代
  2. struct ListNode* reverseList(struct ListNode* head){
  3.     if(head==NULL)
  4.         return NULL;
  5.     struct ListNode* prev,*cur,*next;
  6.     prev=NULL,cur=head,next=head->next;
  7.     while(cur)
  8.     {
  9.         //反转
  10.         cur->next=prev;
  11.         //迭代
  12.         prev=cur;
  13.         cur=next;
  14.         if(next)
  15.             next=next->next;
  16.     }
  17.     return prev;
  18. }

法二：头插

为什么能想到头插呢？因为头插的顺序与链表的顺序刚好相反。

正确代码2：

  1. //头插
  2. struct ListNode* reverseList(struct ListNode* head){
  3.     struct ListNode* cur=head, *newhead=NULL;
  4.     while(cur)
  5.     {
  6.         struct ListNode* next=cur->next;
  7.         //头插
  8.         cur->next=newhead;
  9.         newhead=cur;
  10.  
  11.         cur=next;
  12.     }
  13.     return newhead;
  14. }

合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/

法一：不带哨兵位头结点

  1. //不带哨兵位头结点
  2. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  3.     struct ListNode* cur1=list1,*cur2=list2;
  4.     struct ListNode* head=NULL,*tail=NULL;
  5.     while(cur1&&cur2)
  6.     {
  7.         if(cur1->val<cur2->val)
  8.         {
  9.             if(head==NULL)
  10.             {
  11.                 head=tail=cur1;
  12.             }
  13.             else
  14.             {
  15.                 tail->next=cur1;
  16.                 tail=tail->next;
  17.             }
  18.             cur1=cur1->next;
  19.         }
  20.         else
  21.         {
  22.             if(head==NULL)
  23.             {
  24.                 head=tail=cur2;
  25.             }
  26.             else
  27.             {
  28.                 tail->next=cur2;
  29.                 tail=tail->next;
  30.             }
  31.             cur2=cur2->next;
  32.         }
  33.     }
  34.     if(cur1)
  35.     {
  36.         tail->next=cur1;
  37.     }
  38.     if(cur2)
  39.     {
  40.         tail->next=cur2;
  41.     }
  42.     return head;
  43. }

正确代码1：

  1. //不带哨兵位头结点
  2. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  3.     //如果链表为空，返回另一个
  4.     if(list1==NULL)
  5.     {
  6.         return list2;
  7.     }
  8.     if(list2==NULL)
  9.     {
  10.         return list1;
  11.     }
  12.     struct ListNode* cur1=list1,*cur2=list2;
  13.     struct ListNode* head=NULL,*tail=NULL;
  14.     while(cur1&&cur2)
  15.     {
  16.         if(cur1->val<cur2->val)
  17.         {
  18.             if(head==NULL)
  19.             {
  20.                 head=tail=cur1;
  21.             }
  22.             else
  23.             {
  24.                 tail->next=cur1;
  25.                 tail=tail->next;
  26.             }
  27.             cur1=cur1->next;
  28.         }
  29.         else
  30.         {
  31.             if(head==NULL)
  32.             {
  33.                 head=tail=cur2;
  34.             }
  35.             else
  36.             {
  37.                 tail->next=cur2;
  38.                 tail=tail->next;
  39.             }
  40.             cur2=cur2->next;
  41.         }
  42.     }
  43.     if(cur1)
  44.     {
  45.         tail->next=cur1;
  46.     }
  47.     if(cur2)
  48.     {
  49.         tail->next=cur2;
  50.     }
  51.     return head;
  52. }

法二：带哨兵位头结点

正确代码2：

  1. //带哨兵位头结点
  2. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  3.     struct ListNode* cur1=list1,*cur2=list2;
  4.     struct ListNode* guard=NULL,*tail=NULL;
  5.     guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
  6.     tail->next=NULL;
  7.     while(cur1&&cur2)
  8.     {
  9.         if(cur1->val<cur2->val)
  10.         {
  11.             tail->next=cur1;
  12.             tail=tail->next;
  13.             cur1=cur1->next;
  14.         }
  15.         else
  16.         {
  17.             tail->next=cur2;
  18.             tail=tail->next;
  19.             cur2=cur2->next;
  20.         }
  21.     }
  22.     if(cur1)
  23.     {
  24.         tail->next=cur1;
  25.     }
  26.     if(cur2)
  27.     {
  28.         tail->next=cur2;
  29.     }
  30.     struct ListNode* head=guard->next;//防止内存泄漏
  31.     free(guard);
  32.     return head;
  33. }

链表分割

题目链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

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

运行一下：

由于牛客不提供用例错误，我们可以转到力扣官网上查。当然了，也可以把我们写的用例往代码带，看看哪出错了。

正确代码：

  1. class Partition {
  2. public:
  3.     ListNode* partition(ListNode* pHead, int x) {
  4.         struct ListNode* lessguard,*lesstail,*greaterguard,*greatertail;
  5.         lessguard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
  6.         greaterguard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
  7.         lesstail->next=greatertail->next=NULL;
  8.  
  9.         struct ListNode* cur=pHead;
  10.         while(cur)
  11.         {
  12.             if(cur->val<x)
  13.             {
  14.                 lesstail->next=cur;
  15.                 lesstail=lesstail->next;
  16.             }
  17.             else
  18.             {
  19.                 greatertail->next=cur;
  20.                 greatertail=greatertail->next;
  21.             }
  22.             cur=cur->next;
  23.         }
  24.         lesstail->next=greaterguard->next;
  25.         greatertail->next=NULL;//不能忽略
  26.         pHead=lessguard->next;
  27.         free(greaterguard);
  28.         free(lessguard);
  29.         return pHead;
  30.     }
  31. };

链表的回文结构

题目链接：https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

正确代码：

  1. //找中间节点
  2. struct ListNode* middleNode(struct ListNode* head) {
  3.     struct ListNode* slow = head, *fast = head;
  4.     while (fast && fast->next) {
  5.         slow = slow->next;
  6.         fast = fast->next->next;
  7.     }
  8.     return slow;
  9. }
  10. //反转
  11. struct ListNode* reverseList(struct ListNode* head) {
  12.     struct ListNode* cur = head;
  13.     struct ListNode* newhead = NULL;
  14.     while (cur) {
  15.         struct ListNode* next = cur->next;
  16.         //头插
  17.         cur->next = newhead;
  18.         //迭代
  19.         newhead = cur;
  20.         cur = next;
  21.     }
  22.     return newhead;
  23. }
  24.  
  25. class PalindromeList {
  26.   public:
  27.     bool chkPalindrome(ListNode* A) {
  28.         struct ListNode* mid=middleNode(A);
  29.         struct ListNode* rHead=reverseList(mid);
  30.  
  31.         struct ListNode* curA=A;
  32.         struct ListNode* curR=rHead;
  33.         while(curA&&curR)
  34.         {
  35.             if(curA->val!=curR->val)
  36.             {
  37.                 return false;
  38.             }
  39.             else
  40.             {
  41.                 curA=curA->next;
  42.                 curR=curR->next;
  43.             }
  44.         }
  45.         return  true;
  46.     }
  47. };

相交链表

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

正确代码：

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode* tailA=headA,*tailB=headB;
  3.     int lenA=0,lenB=0;
  4.     while(tailA)
  5.     {
  6.         lenA++;
  7.         tailA=tailA->next;
  8.     }
  9.     while(tailB)
  10.     {
  11.         lenB++;
  12.         tailB=tailB->next;
  13.     }
  14.  
  15.     //不相交的情况,不写的话leetcode也不会判错
  16.     if(tailA!=tailB)
  17.     {
  18.         return NULL;
  19.     }
  20.  
  21.     int gap=abs(lenA-lenB);
  22.     struct ListNode* longList=headA,*shortList=headB;
  23.     if(lenA<lenB)
  24.     {
  25.         longList=headB;
  26.         shortList=headA;
  27.     }
  28.  
  29.     while(gap--)
  30.     {
  31.         longList=longList->next;
  32.     }
  33.  
  34.     while(longList!=shortList)
  35.     {
  36.         longList=longList->next;
  37.         shortList=shortList->next;
  38.     }
  39.     return shortList;
  40. }

环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/

正确代码：

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

环形链表II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

法一：双指针

正确代码1：

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

法二:转化成链表相交

正确代码2：

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode* tailA=headA,*tailB=headB;
  3.     int lenA=0,lenB=0;
  4.     while(tailA)
  5.     {
  6.         lenA++;
  7.         tailA=tailA->next;
  8.     }
  9.     while(tailB)
  10.     {
  11.         lenB++;
  12.         tailB=tailB->next;
  13.     }
  14.  
  15.     //不相交的情况,不写的话leetcode也不会判错
  16.     if(tailA!=tailB)
  17.     {
  18.         return NULL;
  19.     }
  20.  
  21.     int gap=abs(lenA-lenB);
  22.     struct ListNode* longList=headA,*shortList=headB;
  23.     if(lenA<lenB)
  24.     {
  25.         longList=headB;
  26.         shortList=headA;
  27.     }
  28.  
  29.     while(gap--)
  30.     {
  31.         longList=longList->next;
  32.     }
  33.  
  34.     while(longList!=shortList)
  35.     {
  36.         longList=longList->next;
  37.         shortList=shortList->next;
  38.     }
  39.     return shortList;
  40. }
  41.  
  42.  
  43. struct ListNode *detectCycle(struct ListNode *head) {
  44.     struct ListNode* slow=head,*fast=head;
  45.     while(fast&&fast->next)
  46.     {
  47.         slow=slow->next;
  48.         fast=fast->next->next;
  49.         if(slow==fast)
  50.         {
  51.             struct ListNode* meetNode=slow;
  52.             struct ListNode* list1=meetNode->next;
  53.             struct ListNode* list2=head;
  54.             meetNode->next=NULL;
  55.             return getIntersectionNode(list1,list2);
  56.         }
  57.     }
  58.     return NULL;
  59. }

复制带随机指针的链表

题目链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

正确代码：

  1. struct Node* copyRandomList(struct Node* head) {
  2.     //1.拷贝结点插入原结点的后面
  3.     struct Node* cur=head;
  4.     while(cur)//遍历整个链表
  5.     {
  6.         //插入
  7.         struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
  8.         copy->val=cur->val;
  9.         struct Node* next=cur->next;
  10.  
  11.         //cur copy next
  12.         cur->next=copy;
  13.         copy->next=next;
  14.  
  15.         cur=next;
  16.     }
  17.     //2.拷贝random结点
  18.     cur=head;
  19.     while(cur)
  20.     {
  21.         struct Node* copy=cur->next;
  22.         if(cur->random==NULL)
  23.         {
  24.             copy->random=NULL;
  25.         }
  26.         else
  27.         {
  28.             copy->random=cur->random->next;
  29.         }
  30.         cur=cur->next->next;
  31.     }
  32.     //3.拆组
  33.     struct Node* copyHead=NULL,*copyTail=NULL;
  34.     cur=head;
  35.     while(cur)
  36.     {
  37.         struct Node* copy=cur->next;
  38.         struct Node* next=copy->next;
  39.  
  40.         //copy尾插
  41.         if(copyHead==NULL)
  42.         {
  43.             copyHead=copyTail=copy;
  44.         }
  45.         else
  46.         {
  47.             copyTail->next=copy;
  48.             copyTail=copyTail->next;
  49.         }
  50.  
  51.         //恢复原链表
  52.         cur->next=next;
  53.         cur=next;
  54.     }
  55.     return copyHead;
  56. }

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览44139 人正在系统学习中
孤单听雨的猫21
微信公众号
小编本人在学习数学和编程过程中的总结和笔
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪