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

数据结构刷题训练——链表篇（一）

作者：weixin_40725706 | 2024-02-18 07:34:34

赞

踩

数据结构刷题训练——链表篇（一）

目录

前言

题目一：链表的中间节点

思路

分析

题解

 题目二：链表中倒数第k个结点

思路

分析

 题解

题目三：合并两个有序链表

思路

分析

题解

 方法二

题解

 题目四：链表的回文结构

思路

分析

题解

总结

前言

        今天我将开启一个新的专栏，数据结构与算法刷题训练营，题目从基础简单题目开始逐步进阶，以便于初学者巩固和运用所学的知识。

题目一：链表的中间节点

 题目描述：

 示例与提示：

 题目链接

链表的中间节点icon-default.png?t=N6B9https://leetcode.cn/problems/middle-of-the-linked-list/description/

 思路

        题目中的链表属于单链表，我们要怎么计算中间节点呢？先遍历一遍链表统计链表节点个数，然后计算出中间节点，再遍历到需要返回的节点。这或许是大多数人能想到的方法。但是这种方法效率太低。今天我向大家介绍一种新的做题思路，这种方法在其他题目中也是适用。

快慢指针法：

        我们可以创建两个指针，一个快指针一次走两步，一个慢指针一次走一步。当快指针走到尾时，返回慢指针就是中间节点。

分析

情况一：

节点为奇数个。

         假设节点有5个，那需要返回的节点就是第3个节点。初始时，两指针都指向第一个节点，慢指针一次走一步，快指针一次走两步。执行一次情况如上图。当快指针走到最后一个节点时就要结束如下图：

 情况二：

节点为偶数个。

         这是已经执行两次后的状态，接下来fast指针继续走：

         fast指向NULL，而slow指向要返回的节点。

题解

         了解完整体思路，我们依据分析中的情况进行编写代码：

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

 

 题目二：链表中倒数第k个结点

 题目描述：

 题目链接

倒数第k个节点icon-default.png?t=N6B9https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

思路

         这道题目依然可以使用快慢指针的方法来寻找倒数第k个节点。先让快指针走k步，然后让两指针同时向后移动，知道快指针遍历完链表结束。

分析

         初始情况下，两指针都指向第一个节点，先让fast指针走k步：

        我们假设要找倒数第3个节点，fast走3步就指向了第四个节点。

         然后两指针开始同时移动：

         当fast指针指向NULL时就结束，此时slow指向的就是倒数第k个节点。

 题解

 根据上述的分析，我们进行编写代码：

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
  2.     struct ListNode* fast=pListHead,*slow=pListHead;
  3.     
  4.         
  5.     for(int i=0;i<k;i++)
  6.     {
  7.         if(fast==NULL)
  8.         {
  9.             return NULL;
  10.         }
  11.         fast=fast->next;
  12.     }
  13.     while(fast)
  14.     {
  15.         fast=fast->next;
  16.         slow=slow->next;
  17.     }
  18.     return slow;
  19. }

        在代码实现时要注意特殊情况，如果链表为NULL或者k大于链表长度，传进来就要进行特殊处理。

题目三：合并两个有序链表

 题目描述：

 示例：

 题目链接：

合并两个有序链表icon-default.png?t=N6B9https://leetcode.cn/problems/merge-two-sorted-lists/description/

思路

        题目中给的是升序数组，解题思路就是比较链表元素，取小的进行尾插。思路较为简单。

分析

 接下来我们对整体规划进行分析假设初始时：

         把一个链表的元素插入到另一个链表这样操作太麻烦，所以我们可以重新创建一个头指针，将两个链表上的节点插入到新的链表中，创建新链表时，初始化头和尾都为NULL。

 

         然后进行比较，第一步两个大小相同，任取一个插入：

 

         然后再拿着list2中的第一个节点与list1节点进行比较，插入：

         以此类推不断进行比较尾插。

 

        结束条件就是一个链表为NULL结束 

 

         最后将剩余节点的链表尾插到新链表中，返回新链表的头。

题解

        理解了思路就根据分析的内容进行编写代码：

  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
  2. {
  3.     if(list1==NULL)                //考虑原链表中有空链表的情况。
  4.         return list2;
  5.     if(list2==NULL)
  6.         return list1;
  7.     struct ListNode* head=NULL,*tail=NULL;
  8.     while(list1&&list2)
  9.     {
  10.         if(list1->val > list2->val)//比较大小取小的尾插
  11.         {
  12.             if(head==NULL)         //考虑特殊情况新建链表为NULL时进行特殊处理
  13.             {
  14.                 tail=head=list2;
  15.                 
  16.             }
  17.             else                   //尾插
  18.             {
  19.                 tail->next=list2;
  20.                 tail=tail->next;
  21.             }
  22.             list2=list2->next;    //尾插后继续向后
  23.         }
  24.         else
  25.         {
  26.              if(head==NULL)
  27.             {
  28.               tail=head=list1;
  29.                
  30.             }
  31.            else
  32.            {
  33.                 tail->next=list1;
  34.                 tail=tail->next;
  35.            }
  36.            
  37.             list1=list1->next;
  38.         }
  39.     }
  40.     if(list2==NULL)            //一个链表为NULL时将另一个链表剩余的节点尾插到新链表。
  41.         tail->next=list1;
  42.     else
  43.         tail->next=list2;
  44.     return head;
  45. }

 虽然思路非常简单，但是代码实现却很不容易，需要很多要考虑的特殊情况。

 

 方法二

        和思路一相同，也是比较大小，将小的尾插到新的链表。但是可以使用带头结点的链表，这样再插入时就不需要考虑新链表为NULL时的情况，进行特殊处理。可以更好的简化代码。

题解

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

         注意：原链表中不带头节点，返回时不能返回头节点，需要将头节点释放掉，返回头节点的下一个节点。

 

 题目四：链表的回文结构

题目描述：

 题目链接：

链表的回文结构icon-default.png?t=N6B9https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

思路

        有人可能会想，这不很简单吗？把这个链表反转一下，再和原链表数据依次比较不就解决了，但是这里注意题目要求。

        题目要求时间复杂度为O(N)，空间复杂度为O(1)，上述思路需要将原链表复制一份后才可以与逆置是链表进行比较，空间复杂度为O(N)。

        这道题的思路是这样的，可以先找到链表的中间节点，然后从中间节点开始，对后部分的链表进行逆置，然后从中间开始与开头的节点对比，看两个值是否相同。

分析

 情况一：

         节点为偶数个，把后半部分节点逆置，然后依次比较，这里注意其实前半部分的2节点的next这时依然指向的是后半部分的2，后半部分的2节点的next指向NULL。如下图：

 逆置之后，返回的是后半部分1节点的地址，然后进行遍历，直到为NULL结束。

情况二：

        节点数量为奇数个

 实际情况和上述一样：

         但这里在比较的时候就要注意一下3节点，这里不需要把前半部分2节点的next置为NULL，当遍历到最后时，都遍历到了3节点一定是相同的

题解

        当然这些逆置、找中间节点的接口我们已经写过了，可以CV一下前边的代码，这样写代码还是很舒服的Ctrl+C、Ctrl+V

        当然借此我再介绍一种新的逆置链表的方法，我们可以使用头插来实现链表逆置。将原链表的节点依次头插到新的节点，这样就轻松实现了逆置。

代码如下：

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

 整体题解：

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

 

 

总结

        好的本期内容到此结束，后续我将会分享更多数据结构相关的题目，通过画图逐步分析，来帮助大家刷题，这些题目建议大家先做一遍，然后看思路与分析，一定要动手敲一敲代码。最后，感谢阅读!

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

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

  

闽ICP备14008679号