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

顺序表、链表刷题指南（力扣OJ）

作者：Cpp五条 | 2024-06-01 21:18:02

赞

踩

顺序表、链表刷题指南（力扣OJ）

前言

        无论是面试准备还是日常编码实践，解决与顺序表和链表相关的算法问题都是不可避免的挑战，本篇文章旨在帮助你巩固和提升这两个重要数据结构的理解和应用能力。

题目一：删除有序数组中的重复项

 题目描述：

 示例与提示：

 思路：

         题目中的数组是一个升序的数组，依据这个点，我们可以知道，相同的元素都是紧挨着的，那要想保持升序，后一个元素一定不等于当前元素，且一定比当前元素大。和前边删除元素的思路类似，可以直接在原数组中进行操作。

题解：

  1. int removeDuplicates(int* nums, int numsSize){
  2. int pos=0;int src=0;
  3.     while(src<numsSize-1)
  4.     {
  5.         if(nums[src]!=nums[src+1])
  6.         {
  7.             nums[pos++]=nums[src++];
  8.         }
  9.         else
  10.         src++;
  11.     }
  12.     nums[pos++]=nums[src];//为了防止数组越界访问，导致最后一个元素没有进行赋值，最后在这里补上
  13.     return pos;
  14. }

 

题目二：合并两个有序数组

 题目描述：

 示例与提示：

         合并两个有序数组的思想叫做归并，这种思路在后续的学习中也会经常遇到。有的同学可能会有这样的思路，将两个元素合并，然后qsort排序一下，这样暴力求解。这样解题也可以，但我们学习了空间复杂度和时间复杂度，就要考虑到复杂度问题，以写出好的程序。

 思路：

         注意：题目中给的是非递减排列的整数数组，举个例子：1，3，4，5，7。这样的数组属于递增数组，1，2，3，3，3，5，6。这样的数组属于非递减数组。

         了解清楚题意后，我们介绍一下解题思路，我们可以依次比较两数组中的元素，然后把小的尾插到新数组，这个就是归并的思想。但是这道题目有点不一样，它的第一个数组会很大，是两个数组有效数据个数的和，这里就要求我们把数据归并到第一个数组。

那这道题应该怎么解决呢？

        前边介绍的归并思想，我们是正着比较，然后尾插，那这道题，我们是不是可以倒着比较，然后尾插到第一个数组。

 分析：

        理解了解题的思路后，我们在进行更深一步的分析，由于力扣的题目大都是接口型题目，在调试时会很麻烦，这就是我们刷不动题的原因之一，做好全面的分析才能更高效的解决问题。

 情况一：

 

 从末尾开始，依次比较，较大的数字插入到数组一的末尾：

 

 依次比较，并进行插入。

 情况二：

         两个数组依然是末尾数据进行比较，然后尾插到数组一，但是这次不同的是，数组一遍历完后，还并没有结束，此时的数据如下：

         这里就需要再将数组二剩下的数据继续插入到数组一当中。

 题解：

  1. void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
  2. int end1=m-1;
  3. int end2=n-1;
  4. int end=m+n-1;
  5.     while(end1>=0 && end2>=0)
  6.     {
  7.         if(nums1[end1] > nums2[end2])
  8.         {
  9.             nums1[end--]=nums1[end1--];
  10.         }
  11.         else
  12.         {
  13.             nums1[end--]=nums2[end2--];
  14.         }
  15.     }
  16.     while(end2 >=0)
  17.         {
  18.              nums1[end--] = nums2[end2--];
  19.         }
  20. }

         使用3个变量，依次存储第一个数组的有效数据的末尾，第二个数组的末尾，以及第一个数组的末尾。谁大就把他插入到nums1的末尾，最后如果第二个数组没有遍历完，就将剩余数据依次插入到nums1中。

题目三：反转链表

 题目描述：

 思路：

         数组的反转很简单，最后一个元素和第一个元素交换，然后一个往前，一个往后循环遍历，但这个是单链表，没法向前遍历。那要怎么解决呢？我们可以这样做，遍历这个链表，将每个节点依次改为指向前一个节点，但要确保后续节点不丢失。这里我们就可以创建3个结构体指针，一个指向NULL，一个指向第一个节点，最后指向第二个节点，以便于记录链表后续节点。

分析：

        假设初始是这样的一个链表：

         创建3跟结构体指针，改变节点指向后，向后遍历：

         有人疑惑，链表不是不可以向前遍历吗？那n1怎么到n2的位置？我们可以直接把n2赋值给n1，然后把n3赋值给n2，n3通过指针继续向后遍历。

 当n2为NULL时就结束。

 题解：

 分析之后，我们就进行具体实现：

  1. struct ListNode* reverseList(struct ListNode* head)
  2. {
  3.     struct ListNode* n1,*n2,*n3;
  4.     n1=NULL;
  5.     n2=head;
  6.  
  7.     if(n2!=NULL)
  8.         n3=n2->next;
  9.  
  10.     while(n2)
  11.     {
  12.         n2->next=n1;
  13.  
  14.         n1=n2;
  15.         n2=n3;
  16.  
  17.         if(n3!=NULL)
  18.             n3=n3->next;
  19.     }
  20.     return n1;
  21. }

 需要注意的是空指针问题，当n3为空时就不要继续向后遍历了。

 

 题目四：移除链表元素

 题目描述：

 思路一：

        这里的思路中规中矩，遍历这个链表，与遇到要删除的val值就删除，但这里需要注意一点特殊情况，尽可能的去多虑特殊情况。

 分析：

         假设初始时给这样一个链表，要删除的是6.

         但是单一的使用指针找到了val的节点，又没法删，需要知道前一个节点。那可不可以使用替换法，把4替换到6节点的位置，遇到val值节点就把后一个节点替换过来，这样就不用使用两个指针了，但如果要删除的节点是尾节点呢？它可没有后一个节点。所以我们还是使用传统的方法。创建一个指针记录前一个节点。

         把val值前一个节点next改为val后一个节点的地址，释放掉cur指向的节点。如果删除节点是最后一个，将prev指向节点的next置为NULL。

         那这种情况呢？如果要删除的节点是头，prev就行不通了。所有我们还需要再多考虑一下头节的情况，进行特殊处理。

        初始情况下cur和head都指向头节点，把cur的下一个节点赋值为head，然后释放掉cur指向的第一个节点，再把新的头head赋给cur。这样就可以解决了。

题解：

        分析完整体思路后，我们进行代码实现，代码如下：

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

 思路二：

        除了传统的方法，还有另外一种方法——尾插法。遍历原链表，如果不是val就尾插到新链表。

分析：

        可以先创建一个新的链表头，初始时链表头为空，然后依次尾插，插入节点。

         这种方法更加简单快捷，没有那么多需要考虑的特殊情况，最后返回新的头。

题解：

        这种方法思路虽然很简单，但在实现时有很多需要注意的点：

  1. struct ListNode* removeElements(struct ListNode* head, int val)
  2. {
  3.     struct ListNode* cur=head;
  4.     struct ListNode* newhead=NULL,*tail=NULL;
  5.     while(cur)
  6.     {
  7.         if(cur->val==val)
  8.         {
  9.             struct ListNode* del=cur;
  10.             cur=cur->next;
  11.             free(del);
  12.         }
  13.         else 
  14.         {
  15.             if(tail==NULL)//考虑初始时头和尾都为NULL的情况
  16.             {
  17.                 tail=newhead=cur;
  18.             }
  19.             else
  20.             {
  21.                 tail->next=cur;
  22.                 tail=tail->next;
  23.                 
  24.             }
  25.             cur=cur->next;
  26.         }
  27.     }
  28.     if(tail)
  29.         tail->next=NULL;//遍历完之后需要将尾节点next置为NULL，此外还需要注意tail是否为NULL。
  30.  
  31.     return newhead;
  32. }

         在刷题时我们会发现，很多的操作都是基于我们前边学习的单链表中基本操作的变形，此外解题的思路在很多情况下都是通用的，只需略微变形就可解决问题。所有一定要学会举一反三。

总结

        刷题不仅是为了应对面试和编码实践，更是为了培养自己的问题解决能力和学习能力。无论是顺序表还是链表，它们都是构建更复杂数据结构的基石，掌握它们对你的编程之路至关重要。最后，感谢阅读！

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

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

  

闽ICP备14008679号