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

【数据结构】图文详解11道力扣链表OJ题_链表编程题

作者：繁依Fanyi0 | 2024-04-24 08:04:01

赞

踩

链表编程题

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

 一、移除链表元素

二、反转链表

三、链表的中间节点

四、链表中倒数第k个节点

五、合并两个有序列表

六、链表分割

七、回文链表

八、相交链表

九、环形链表

十、环形链表 II

1、思路一

2、思路二

十一、复制带随即指针的链表

1、思路

2、代码

一、移除链表元素

1、思路

新建一个哨兵位，用cur指针遍历原链表，cur->val!=val,将该节点连接至哨兵链表，反之释放。迭代遍历原链表即可，最后记得将哨兵链表的尾节点的next置空！！！

2、代码

  1. struct ListNode* removeElements(struct ListNode* head, int val){
  2.     struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
  3.     struct ListNode* guardcur=guard;//用于记录哨兵链表的尾插
  4.     struct ListNode* cur=head;//用于原链表的遍历
  5.     while(cur)
  6.     {
  7.         struct ListNode* next=cur->next;
  8.         if(cur->val!=val)
  9.         {
  10.            guardcur->next=cur;
  11.            guardcur=cur;
  12.         }
  13.         else 
  14.         {
  15.             free(cur);
  16.         }
  17.             cur=next;
  18.     }
  19.     guardcur->next=NULL;//最后需要把尾节点的next置空
  20.     head=guard->next;
  21.     free(guard);//记得释放哨兵位
  22.     return head;
  23. }

二、反转链表

1、思路

遍历原链表，将每一个节点取下来，不断头插反转链表

2、代码

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

三、链表的中间节点

1、思路

思路1：可以遍历计数找中间节点

思路2：快慢指针，快指针走两步，慢指针走一步，快指针走到尾节点或者空节点，慢指针就指向链表的中间节点

2、代码

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

注意，while循环内两个条件的顺序不能颠倒。如果颠倒，当fast为NULL时，先判断fast->next!=NULL，这是一个对空指针解引用的问题！

四、链表中倒数第k个节点

1、思路

定义快慢指针，不难发现，快指针需要比慢指针快k-1步，所以先让快指针向前走k-1步，判断fast==NULL是防止原链表为空，判断fast->next=NULL是因为，后面fast=fast->next，说明k大于链表长度。

2、代码

  1. struct ListNode* getKthFromEnd(struct ListNode* head, int k){
  2.     struct ListNode* fast=head,*slow=head;
  3.     int tmp=k-1;//快慢指针相差的距离
  4.     while(tmp--)
  5.     {
  6.         if(fast==NULL||fast->next==NULL)//考虑下值大于节点个数的问题
  7.             return NULL;
  8.         fast=fast->next;
  9.     }
  10.     while(fast->next)
  11.     {
  12.         fast=fast->next;
  13.         slow=slow->next;
  14.     }
  15.     return slow;
  16. }

五、合并两个有序列表

1、思路

创建一个哨兵节点，用两个指针分别指向原链表，将val小的节点尾插即可。记得释放哨兵位。

2、代码

  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  2.     struct ListNode* cur1=list1,*cur2=list2;
  3.     struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode));
  4.     struct ListNode* guardcur=guard;
  5.     struct ListNode* small,*big;
  6.     while(cur1!=NULL&&cur2!=NULL)
  7.     {
  8.         if(cur1->val>cur2->val)
  9.         {
  10.             small=cur2;
  11.             big=cur1;
  12.             cur2=cur2->next;
  13.         }
  14.         else
  15.         {
  16.             small=cur1;
  17.             big=cur2;
  18.             cur1=cur1->next;
  19.         }
  20.         guardcur->next=small;
  21.         guardcur=small;
  22.     }
  23.     if(cur1==NULL)
  24.     {
  25.         guardcur->next=cur2;
  26.     }
  27.     else
  28.     {
  29.         guardcur->next=cur1;
  30.     }
  31.     struct ListNode* head=guard->next;
  32.     free(guard);
  33.     return head;
  34. }

六、链表分割

1、思路

创建两个哨兵位，遍历原链表，将val小于x和大于等于x的节点分别尾插至两个哨兵链表，再将两个链表连接起来。注意要把大的哨兵链表的尾指针置空。

2、代码

  1. class Partition {
  2. public:
  3.     ListNode* partition(ListNode* pHead, int x) {
  4.         ListNode* guard1=(ListNode*)malloc(sizeof(ListNode));//哨兵位1
  5.         ListNode* guard2=(ListNode*)malloc(sizeof(ListNode));//哨兵位2
  6.         ListNode* small=guard1,*big=guard2;
  7.         ListNode* cur=pHead;//用于遍历链表
  8.         while(cur)
  9.         {
  10.             if(cur->val<x)
  11.             {
  12.                 small->next=cur;
  13.                 small=small->next;
  14.                 cur=cur->next;
  15.             }
  16.             else
  17.             {
  18.                 big->next=cur;
  19.                 big=big->next;
  20.                 cur=cur->next;
  21.             }
  22.         }
  23.         big->next=NULL;
  24.         small->next=guard2->next;//链接两个链表
  25.         free(guard2);
  26.         pHead=guard1->next;
  27.         free(guard1);
  28.         return pHead;
  29.     }
  30. };

七、回文链表

1、思路

1、找出中间节点（本文题三）

2、对后半段进行逆置（本文题二）

3、比对val是否相等，当逆置指针为空，比对结束

2、代码

  1. bool isPalindrome(struct ListNode* head){
  2.     //先用快慢指针找到中间节点
  3.     struct ListNode* fast=head,*slow=head;
  4.     while(fast!=NULL&&fast->next!=NULL)
  5.     {
  6.         slow=slow->next;
  7.         fast=fast->next->next;
  8.     }
  9.     //现在slow是中间节点
  10.     //反转后半部分链表
  11.     struct ListNode* newnode=NULL;
  12.     struct ListNode* cur=slow;
  13.     while(cur)
  14.     {
  15.         struct ListNode* next=cur->next;
  16.         cur->next=newnode;
  17.         newnode=cur;
  18.         cur=next;
  19.     }
  20.     //比较
  21.     fast=head;
  22.     slow=newnode;
  23.     while(slow)//fast和slow会同时为空或slow先空
  24.     {
  25.         if(fast->val!=slow->val)
  26.             return false;
  27.         fast=fast->next;
  28.         slow=slow->next;
  29.     }
  30.     return true;
  31. }

八、相交链表

1、思路

1、分别遍历链表，算出两个链表的长度。

2、让长链表先往前走，走到和短链表一样长

3、两个链表再同时走，走到两个指针一样即为相交点，如果走到空还没有找到，则不相交

2、代码

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode* curA=headA,*curB=headB;//用于遍历链表
  3.     int lenA=1,lenB=1;//统计A和B的长度
  4.     while(curA)
  5.     {
  6.         curA=curA->next;
  7.         ++lenA;
  8.     }
  9.     while(curB)
  10.     {
  11.         curB=curB->next;
  12.         ++lenB;
  13.     }
  14.     int a=abs(lenA-lenB);//A和B链表长度的差值
  15.     struct ListNode* longlist=headA,*shortlist=headB;//设两个节点
  16.     if(lenA<lenB)//通过一个判断，让longlist指向较长的链表
  17.     {
  18.         longlist=headB;
  19.         shortlist=headA;
  20.     }
  21.     while(a--)//让较长的链表先把差值走掉
  22.     {
  23.         longlist=longlist->next;
  24.     }
  25.     while(longlist)
  26.     {
  27.         if(longlist==shortlist)
  28.             return longlist;
  29.         longlist=longlist->next;
  30.         shortlist=shortlist->next;
  31.     }
  32.     return NULL;
  33. }

九、环形链表

1、思路

定义快慢指针，快指针一次走两步，慢指针一次走一步，如果相遇，说明有环，当快指针等于NULL，说明没环

2、代码

  1. bool hasCycle(struct ListNode *head) {
  2.     //快指针一次走两步，慢指针一次走一步，快指针先进环，慢指针后进环，相对静止
  3.     //能追上说明有环，有一个指针为空说明没环
  4.     struct ListNode* fast=head,*slow=head;
  5.     while(fast&&fast->next)//这里不用判断slow是否为空，不管带不带环，slow没有机会为空
  6.     {
  7.         fast=fast->next->next;
  8.         slow=slow->next;
  9.         if(fast==slow)
  10.             return true;
  11.     }
  12.     return false;
  13. }

十、环形链表 II

1、思路一

1、定义快慢指针，快指针一次走两步，慢指针一次走一步,找到相遇点（本文题九）

2、将相遇点的后一个节点当成另一个链表的头结点，问题转化为本文题八

2、代码

  1. struct ListNode *detectCycle(struct ListNode *head) {
  2.     //先找到相遇点
  3.     struct ListNode* fast=head,*slow=head;
  4.     while(fast&&fast->next)
  5.     {
  6.         fast=fast->next->next;
  7.         slow=slow->next;
  8.         if(fast==slow)
  9.             break;
  10.     }
  11.     if(fast==NULL||fast->next==NULL)
  12.         return NULL;
  13.  
  14.     struct ListNode* headA=fast->next;//两个链表的头结点
  15.     struct ListNode* curA=headA;//cur用于遍历统计链表长度
  16.     struct ListNode* headB=head;
  17.     struct ListNode* curB=headB;
  18.     int lenA=1,lenB=1;
  19.     while(curA!=fast)
  20.     {
  21.         curA=curA->next;
  22.         ++lenA;
  23.     }
  24.      while(curB!=fast)
  25.     {
  26.         curB=curB->next;
  27.         ++lenB;
  28.     }
  29.     struct ListNode* longlist=headA,*shortlist=headB;
  30.     if(lenA<lenB)
  31.     {
  32.         longlist=headB;
  33.         shortlist=headA;
  34.     }
  35.     int a=abs(lenA-lenB);//长度的差值
  36.     while(a--)
  37.     {
  38.         longlist=longlist->next;
  39.     }
  40.     while(1)
  41.     {
  42.         if(longlist==shortlist)
  43.             return longlist;
  44.         longlist=longlist->next;
  45.         shortlist=shortlist->next;
  46.     }
  47. }

3、思路二

1、设进环前的长度为L，入环点到相遇点的距离为X，环的长度为R

2、两指针相遇时，slow走的距离是L+X，fast走的距离是L+N*R+X，N为fast指针在环里绕的圈数（注意这里N一定大于等于1，因为快慢指针在环内相遇，说明快指针和慢指针相遇前，快指针起码路过了一次相遇点）（而且当慢指针进环后，快指针肯定会一圈追上慢指针，因为快指针比慢指针每次多走一步，相对静止，走一圈的距离必定追上）

3、那么2*（L+X)=L+N*R+X，化简得L=N*R-X，再化简得L=(N-1)*R+R-X

4、可得结论：一个指针从头结点开始走，另一个指针从相遇点开始走，那么他们会在入口处相遇

4、代码

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

十一、复制带随即指针的链表

1、思路

题目要求是复制一个一模一样的链表，难点在于random指针的控制

1、在每个节点后边插入一个节点，复制对应的val

2、再复制random指针，复制时要分空和非空情况，对于空，复制节点random为NNULL；非空，

则为cur->next->random=cur->random->next

3、再创建两个哨兵节点，将原链表与复制链表节点分开。

2、代码

  1. struct Node* copyRandomList(struct Node* head) {
  2. 	struct Node* cur=head;
  3.     while(cur)//插入复制节点
  4.     {
  5.         struct Node* next=cur->next;
  6.         struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
  7.         cur->next=newnode;
  8.         newnode->val=cur->val;
  9.         cur=next;
  10.         newnode->next=cur;
  11.     }
  12.     cur=head;
  13.     while(cur)//复制random指针
  14.     {
  15.         if(cur->random==NULL)
  16.             cur->next->random=NULL;
  17.         else
  18.         {
  19.             cur->next->random=cur->random->next;
  20.         }
  21.         cur=cur->next->next;
  22.     }
  23.     //将链表复原
  24.     cur=head;
  25.     struct Node* guard=(struct Node*)malloc(sizeof(struct Node));
  26.     struct Node* guardcopy=(struct Node*)malloc(sizeof(struct Node));
  27.     guardcopy->next=NULL;
  28.     struct Node* curA=guard,*curB=guardcopy;
  29.     int count=1;
  30.     while(cur)
  31.     {
  32.         struct Node* next=cur->next;
  33.         if(count%2==1)
  34.         {
  35.             curA->next=cur;
  36.             curA=cur;
  37.         }
  38.         else
  39.         {
  40.             curB->next=cur;
  41.             curB=cur;
  42.         }
  43.         cur=next;
  44.         ++count;
  45.     }
  46.     curA->next=NULL;
  47.     struct Node* newhead=guardcopy->next;
  48.     free(guardcopy);
  49.     free(guard);
  50.     return newhead;
  51. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/478382
推荐阅读
相关标签

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

  

闽ICP备14008679号