顺序表、链表刷题指南力扣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.  
    }

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

---

总结

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

这篇好文章是转载于：学新通技术网