LeetCode链表练习（上）

前言

之前介绍了链表的实现，为了更好巩固所学的知识，刷题是很有必要的。
本文将讲解一些比较简单且经典的链表力扣题，灵活运用链表知识来解题。

---

1.反转链表

1.题目分析

题目链接直接点击

这个题有多种解法，我介绍两种。第一种做法：题目要求我们反转这个链表，我们直接将原链表节点头插到新的链表上，构建一条新链表不就解决了。

我们将原来链表上的每个节点拿下来，然后头插到新链表上就行了。之前我们实现链表的时候都是通过malloc函数申请一个节点空间。这道题直接有现成的节点拿下来即可。

第二种方法：链表都是通过节点中的地址域中的地址连接起来的，我们只要改变节点中指针的指向，就可以改变节点的指向。

我们知道实际上在链表中是不存在这个箭头的，这个箭头是我们逻辑上的结构。这个箭头实际上用地址域中的指针来表示的，我们先将原来链表每个节点先断开，在改变每个节点的指向，最后返回最后一个节点即可。最后一个节点相当于成了链表的头节点。

---

2.代码示例

第一种头插法

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

遍历整个链表，将cur的next提前保存，cur的next指向新链表头节点，然后头节点更新。这段操作就是头插实现更新头的常规操作，cur更新继续往前走直到遍历完这个链表的节点。当原链表是空时，new_head也是空，这种情况也可以适用。

---

第二种方法

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*p1=NULL;
    struct ListNode*p2=head;
    struct ListNode*p3=head->next;
    while(p2)
    {   
        p2->next=p1;
        p1=p2;
        p2=p3;
        if(p3)
        {
            p3=p3->next;
        }
    }
  return p1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第二种方法思路简单但是要注意的细节还是很多的.首先我们断开节点之间的连接之前，要先保存原来一个节点的地址，不然断开后就找不到后续的节点了。其次应该有个变量来保存最后的返回值和一个专门来遍历整个链表节点的变量。这就需要3个变量来各司其职，其实两个变量也是可以的，但是这样做看起来逻辑不够清晰。遍历循环结束的条件是什么呢？我们画图来分析一下

那为什么循环条件不能写成n3为空的时候结束呢？这是因为n2 必须先改原来节点才能继续往前移动，也就是说改变节点指向后，n3就要更新，然后n2迭代往后走。如果n3为空就结束循环，这个时候n2只是改变了倒数第二个节点指向，还有最后一个节点没有改就结束循环了，为了保证每个节点的指向都会被更新，n2为空的时结束循环.同时当链表为空的时候这种情况要单独判断。每次循环时n1都会被n2赋值更新，所以当n2为空时，n1就是最后一个节点，也就是反转后的链表头节点。

第二种方法更注意细节，在不确定循环结束条件和各种指针变量的指向时可以画图来理解分析

---

2.力扣203. 移除链表元素

1.题目分析

题目链接直接点击

这道移除链表元素的题，也介绍两种方法。第一种方法：就是挨个遍历链表节点，原地删除数据，这个方法就和之前删除数组元素方法差不多。定义两个指针变量，一个向前遍历比对，另一个用来将符合要求的节点以新的指向关系链接起来。这种就是双指针处理方式。

第二种方法：我们可以采用尾插法来解决。如果某个节点的val不等于指定的整数，我们直接将改节点从原链表上拿下来，组成新新链表的节点，遍历完原链接的每个节点，新链表就是移除指定元素后的链表。这个思路和之前那道题的思路很像，只不过这个是尾插，那个是头插。

---

2.代码示例

双指针原地删除

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode*removeElements(struct ListNode* head,int val)
{

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

首先我们要考虑比较特殊的情况，当遇到的节点是删除的节点时，如果这个节点是头节点，这个时候prive还是空指针，这个时候prev就是空指针，空指针是不能解引用的，这个情况就相当于头删。需要单独处理，如果不是头删，就直接将prive的next指向cur的next，重新建立节点的指向关系，然后更新cur继续遍历。遇到的节点不是要删除的节点，prev和cur继续迭代向前走即可。如果原链表是空链表，这样的处理方式也是适用的。

---

尾插法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode*removeElements(struct ListNode* head,int val){
       struct ListNode* new_head=NULL;
       struct ListNode*tail=NULL;
       struct ListNode*cur=head;
       while(cur)
       {
           if(cur->val!=val)
            {
                if(new_head==NULL)
                 {
                     new_head=tail=cur;
                 }
                 else
                 {
                     tail->next=cur;
                     tail=cur;
                 }
                cur=cur->next;
            }
            else
            {
                struct ListNode* temp=cur->next;
                free(cur);
                cur=temp;
            }
       }
       if(tail)
        {
            tail->next=NULL;
        }
   return new_head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

这个尾插法处理方式和之前实现单链表的尾插是差不多的，new_head是新链表的头节点，tail表示新链表尾节点，cur来遍历整个原链表的节点，当遇到的节点不是要删除的节点时，只用将节点拿下来挂到新节点上即可，直到cur遍历结束。注意当new_head==NULL时，需要单独处理，将节点挂在新链表上，此时只有一个节点链表头和链表尾都是它自己。当new_head不为空时，只需要将更新链表尾节点tail进行更新即可。当将最后一个节点挂到新链表上时，tail的next指向是已经被删除了的节点地址，这个时候tail的next是需要手动指向空的。当链表为空时或者链表中的所有元素都是要删除的节点时，tail和new_head一直都会指向空，如果tail解引用就是对空指针解引用，这就会引发问题。所有需要加个if语句处理判断一下即可。
关于尾插为介绍一种比较好的处理方式，就是创建一个哨兵位来处理。这个哨兵位和循环链表中哨兵位的用法差不多，都是不用存储数据。哨兵位的next指向存储有效数据第一个节点，也就相当于无头单链表的头节点。当没有数据时，尾节点就是哨兵位。有了哨兵位的好处是不用再来对头节点进行空处理。也不用对尾节点进行判断。

之所以不用判空处理是因为带了哨兵位，现在第二个节点才是原来单链表的头节点，就相当于链表始终有个节点空位，只管拿节点尾插到新链表即可。当原链表所有节点都是要删除的节点或者链表是空时，这个时候尾节点就是哨兵位，哨兵位是malloc出来的节点，不用担心空指针解引用的问题。哨兵位的next是相当于头节点，也就是tail的next是头节点，这个时候返回哨兵位的next就是返回空指针，也是正确的处理方式。因为哨兵位是malloc出来的所以需要创建一个临时变量来保存一下哨兵位的next，然后再释放哨兵位的空间。

---

3.力扣876. 链表的中间结点

1.题目分析

题目链接直接点击

这道题也介绍两种方法。第一种方法：先遍历整个链表，同时用一个变量来计数。这样直接得到了节点的个数，再接着遍历链表，遍历次数是节点个数的一半，最后结束遍历时的节点就是所求的节点

第二种方法就是快慢指针，设置两个指针变量都指向头节点。然后慢指针走一步，快指针走两步，当快指针走到链表尾节点处，慢指针就走到了中间节点处。

---

2.代码示例

遍历计数

struct ListNode* middleNode(struct ListNode* head){
    int count=0;
   struct ListNode* cur=head;
    while(cur)
    {
        cur=cur->next;
        count++;
    }
    cur=head;
    count/=2;
    while(count--)
    {
        cur=cur->next;
    }
    return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

之前我举个例子是节点个数是奇数，如果节点个数是偶数呢？首先count的初始值是0，但是cur是头节点也就是第一个节点，以节点数6为例，中间的节点是第4个节点，6/2=3，但是因为cur一开始就是第一个节点，所一遍历3次就是第四个节点。以节点数5为例，此时中间节点是第3个节点，5/2是向下取整，也就是等于2，因为cur是头节点所以遍历2次就是第三个节点。不管节点数是偶数都符合题目要求

---

快慢指针

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

快慢指针也只是考虑了链表节点数位奇数的情况，当节点数为偶数应该怎么处理呢？我们再次画图分析一下。

当节点数为偶数时，判断条件是fast不为空，因为fast一次走两步，走到最后刚好就走到空指针处。所以判断条件应该fast不为空，这样slow指针还是指向中间节点。当节点数为奇数时，slow指向中间节点时，fast一定指向尾节点，这个时候应该停止迭代.尾节点的标志就是这个节点的next指向空。判断条件应该是fast->next不为空。只需要将这种两种情况并起来当作循环结束条件即可。最后slow指向的就是中间节点

---

4.链表倒数第k个节点

1.题目分析

题目链接直接点击

这道题力扣也有，但是牛客这道题的测试用例更全一点，所以链接就用的是牛客的。废话不多说，我们先来简单分析一下题目，这道题目和上面寻找中间节点有点像，这道题也是介绍两种做法，第一种还是计数，遍历整个链表，得到节点个数后又开始循环遍历，遍历一次节点数减一，直到节点数减至k结束遍历。此时遍历得到节点就是所求的节点。

第二种方法还是刚才的快慢指针，快慢指针都先指向头节点，先让快指针走k步，然后快慢指针在一起移动。直到快指针遍历完整个节点，此时慢指针指向的节点就是所求的节点。

---

2.代码示例

遍历计数

struct ListNode* FindKthToTail(struct ListNode* pListHead, 
int k ) {
    // write code here
    int count=0;
    struct ListNode* cur=pListHead;
    if(cur==NULL)
     {
         return NULL;
     }
    while(cur)
    {
        cur=cur->next;
        count++;
    }
    if(count<k)
      {
          return NULL;
      }
    cur=pListHead;
    while(count!=k)
    {
        cur=cur->next;
        count--;
    }
  return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

首先用来计数的count初始值为0，但是cur是从头节点开始遍历的，所以在减减的时候就是相当于少减了一次也就是相当于加1了，就不用计数+1在减减了。同时，要注意两种情况，当链表为空的时候直接返回空，当节点数小于k时，这个时候节点数根本不够，也直接返回空即可。

---

快慢指针

struct ListNode* FindKthToTail(struct ListNode* pListHead, 
int k ) {
    // write code here
    struct ListNode* fast=pListHead;
    struct ListNode* slow=pListHead;
    while(k--)
    {
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

快慢指针，在遍历时也需要考虑上述两种特别情况，当k大于节点数和链表为空时的特殊处理。因此在快指针先走的时候，快指针一旦等于空，就直接返回空指针。

---

5.总结

• 1.本文讲解了力扣部分链表经典题，因为篇幅已经有点长了，后续还会继续讲解链表相关题目。
• 2.在做题时候如果有思路了，先别着急写，先画图梳理清楚链表节点之间的关系和移动效果，之后再写代码就不容易出错，一气呵成。
• 3.在需要用到尾插的处理方式时可以适当考虑带哨兵位的插入方式，这个后续会有一道题来讲解。
• 4.以上内容如有错误，欢迎指正！