欢迎各位大佬光临本文章！！！

 

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=blog

我的gitee：冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercool

目录

前言

1.移除链表元素

（1）遍历链表删除元素

（2）无哨兵尾插

（3）带哨兵尾插

2.反转链表

（1）头插

（2）三指针轮转

 3.链表的中间结点

（1）遍历找中间结点

（2）快慢指针

前言

前面说过单链表不会单独的作为数据存储的结构来使用，多半会作为基础讲解对象，还有就是0J 练习题中的题目多半都是单链表结构，下面我们就来盘一盘这些题！！

1.移除链表元素

题目连接：203. 移除链表元素 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

简单来说，这个题类似于在数组中将与给定的数值val相同的元素全部删除，并返回数组本身。只不过这里是链表而已，所以我们自然想到了一种解法，遍历链表然后删除元素。本题举例分析中的删除元素为6。

（1）遍历链表删除元素

首先我们将头指针head赋值给cur，然后cur对链表进行遍历，当cur->val==给定的数值val时，将cur所指向的结点释放，然后将cur赋值给cur->next。如果不相同则cur直接赋值给cur->next。

上面这种只是一般情况，我们还要考虑一些特殊的情况，例如如果head指向的是空链表怎么办，链表元素全是给定的val怎么办？

如果链表为空，我们就直接返回NULL，如果链表元素开头为val我们就让head往后走，直到head指向的val不为所给定的val。然后就像分析的那样进行删除，最后返回head指针。

但是我们发现，我们释放掉结点后，需要将前后的结点连接起来，后面的结点就是cur->next，前面的结点并不好找，所以我们要将前面的结点保存到指针pre之中。

下面是代码以及逐句分析：

具体代码：

struct ListNode* removeElements(struct ListNode* head, int val){    struct ListNode* pre = NULL;    struct ListNode* cur = head;    while ( cur != NULL )    { if ( cur->val == val ) {     if ( cur == head )     {  head = cur->next;  free(cur);  cur = head;     }     else     {  pre->next = cur->next;  free(cur);  cur = pre->next;     } } else {     pre = cur;     cur = cur->next; }    }    return head;}

（2）无哨兵尾插

上面的解法最容易想到，那有没有其他的方法呢？有，例如我们使用尾插的方法，将链表中结点元素不为val 的结点拿下来进行尾插，释放掉val相等的结点，然后将新连接的链表赋值给head。

等cur遍历一遍原链表后，新的链表也尾插完毕，然后返回新链表即可 

值得注意的是，我们需要将尾插的最后一个结点的next要置为NULL，如果不置为NULL，假设原链表的最后一个元素val的值与删除元素相等，那么我们尾插的就是上一个结点，其结点中的next还保存指向原链表最后一个元素的地址，我们将其释放后，必然会造成野指针的问题。

代码如下：

struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* newnode=NULL;    struct ListNode* cur = head;    head = NULL;    //尾插    while ( cur != NULL )    { if ( cur->val == val ) {     struct ListNode* del = cur;     cur = cur->next;     free(del); } else {     if ( newnode == NULL )     {  newnode = head = cur;     }     else     {  newnode->next = cur;  newnode = newnode->next;     }     cur = cur->next; }    }    if ( newnode )    { newnode->next = NULL;    }return head;}

下面我们开始分析这个代码：

注意一下图中黄色框圈起来的代码：head==NULL；这有什么用呢？

如果结点元素val全都是需要删除的元素，例如链表中的val都是6的情况，此时我们会发现，代码进入循环后只会走if语句，将原链表全部删除，然后head保存的还是原来头节点的位置，并非我们要返回的NULL。所以要将其置空处理。

（3）带哨兵尾插

我们发现上面的尾插的方法也没有想象中的这么简单，指向相对好理解了一下。例如我们在处理尾插的时候就要处理两步，判断是否为第一次尾插或者不是第一次尾插，能不能有简单点的尾插方法呢？

答案是有的，就是创建一个哨兵位，不存任何元素，只需要将需要尾插的数据直接连接在后面即可，最后返回哨兵位的next。这样我们就不用在判断是否为第一次尾插，或者是否为全都是删除元素的情况了。

话不多说，直接上代码开始分析：

struct ListNode* removeElements(struct ListNode* head, int val){    //哨兵结点    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));    newnode->next = NULL;    struct ListNode* cur = head;    struct ListNode* tail = newnode;    //尾插    while ( cur != NULL )    { if ( cur->val == val ) {     struct ListNode* del = cur;     cur = cur->next;     free(del); } else {     tail->next = cur;     cur = cur->next;     tail = tail->next; }    }    tail->next = NULL;    struct ListNode* del = newnode;    newnode = del->next;    free(del);    return newnode;}

代码分析：

 使用该方式一定不要忘了释放掉哨兵的结点空间，不然会造成内存泄漏的情况。

2.反转链表

题目链接：206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

题目意思就是让原链表12345经过翻转后变为54321，返回指向新链表的头节点

经过上一个题的具体介绍，我想我们应该很自然的想到开辟新结点进行插入的办法。

（1）头插

这次是头插而不是尾插。我们将原链表中的元素拿过来进行头插，得到的就是翻转的链表。

当然我们要注意空链表的情况，这时我们应该返回空指针。头插解法是最简单的一种解法，直接上代码。

struct ListNode* reverseList(struct ListNode* head){    struct ListNode* cur = head; struct ListNode* new = NULL; while ( cur != NULL ) {     struct ListNode* tmp1 = cur->next;    cur->next = new;     new = cur;     cur = tmp1; }   return new;}

代码分析：

（2）三指针轮转

当然除了头插还有就是在原链表的基础上进行逐步翻转，这就是三指针轮转法。

为什么需要三个指针呢？

首先我们需要一个指针cur对链表进行遍历，然后将cur->next进行翻转，翻转指向cur之前的元素，前面的元素又是谁呢，所以我们需要用pre来记录。随后我们需要将cur变为cur后面的结点，但是next已经被更改为前面的了，谁来记录下一个结点呢？这就需要tmp来记录。

当然我们要先判断head是否为空链表，如果是直接返回NULL。然后在进行翻转。当然cur也不一定指向head，可以指向head->next。

但是cur=cur->next并不是一直进行的，当cur已经移动到NULL 的位置时，对其进行访问操作必然会照成空指针解引用的问题，所以我们要判断，只有当cur不为NULL的时候才能进行移动cur指针。

最后tmp将会指向最后一个元素，也就是反转后的第一个元素。

 代码：

struct ListNode* reverseList(struct ListNode* head){    if ( head == NULL )   {    return head;   } struct ListNode* tmp = NULL; struct ListNode* pre = head; struct ListNode* cur = head->next; while ( pre != NULL ) {     pre->next = tmp;     tmp = pre;     pre = cur;     if(cur!=NULL)     cur = cur->next;      } return tmp;}

 3.链表的中间结点

题目链接：876. 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

看到该题目我们最先想到的就是遍历找中间位置。没错，第一种解法就是这样，但是我们还有一种更绝妙的解题方法。

（1）遍历找中间结点

我们从题目可以得知，链表要分为两种情况考虑，奇数个数和偶数个数。

首先我们需要知道结点的个数count，然后在遍历一遍找到中间位置pos，并将其返回，如果为空链表则返回空指针，如果链表有一个元素，则返回该链表头指针。

代码便很容易写出来：

struct ListNode* middleNode(struct ListNode* head){    if ( (head == NULL)||(head->next==NULL) )    { return head;    }    else    { int count = 0; struct ListNode* cur = head; while ( cur ) {     count++;     cur = cur->next; } int pos = count / 2 + 1; cur = head; count = 1; while ( count != pos ) {     cur = cur->next;     count++; } return cur;    }}

代码分析：

（2）快慢指针

上面的方法虽然好想但是还不够好，因为我们遍历了两遍链表，如果说只能遍历一遍链表呢？

那就得用快慢指针了。我们创建两个指针，一个每次走一步，一个每次走两步，当走两步的走完时，走一步的恰巧为中间位置，然后返回此指针即可。

我们发现奇数个结点的结束标志是fast->next==NULL，偶数个结点则为fast为NULL。

所以代码为：

struct ListNode* middleNode(struct ListNode* head){    struct ListNode* slow;    struct ListNode* fast;    slow = fast = head;    while ( fast && fast->next )    { slow = slow->next; fast = fast->next->next;    }    return slow;}

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖