[数据结构]题海啊，全是水（一）移除链表元素、反转链表、链表的中间节点

这个是目录

菜鸡大学生的数据结构——刷题篇1
自从宇宙大爆炸以来，上课就和课后作业联系起来。大学生不能失去刷题，正如西方不能失去耶路撒冷。 我们的菜鸡大学生也知道这一点，虽然内心有一万个不愿意，但是还是打开了leetcode，破防了三天三夜，编出了这篇文章。

敬请见证…

移除链表元素

给你一个链表的头节点

head

和一个整数

val

，请你删除链表中所有满足

Node.val == val

的节点，并返回 新的头节点 。

示例1：

输入： head = [1,2,6,3,4,5,6], val = 6
输出： [1,2,3,4,5]

示例2：

输入： head = [], val = 1
输出： []

示例3：

输入： head = [7,7,7,7], val = 7
输出： []

分析

无论在什么时候，题目的示例也都是很重要的，它可以给我们考虑到大部分情况，剩下的一小部分则需要我们去思考。
这一题就是这样，通过题目我们可以发现有三种情况：

• 最常见最普通的情况。
• 空链表。
• 链表里面全是要移除的数据。

然后根据我们多年做题的经验，怎么能没有要删除的数据连续出现的情况呢，果断加上，至于以后用不用得到再说。

第一种情况

根据我们写链表的经验，这个不就是pos位置删除数据吗？只不过pos位置变成了满足条件的值。
直接来吧！

逻辑：next，cur和prev三个个指针遍历链表，如果cur的值是要删除的值，prev指向cur的下一位，释放cur，cur指向下一位，直到遍历结束。
我们试着把这套逻辑扔到要删除的数据连续出现这一种情况。发现是可行的（可以自己试着画图验证），于是，我们轻松愉快的解决掉了两种情况。

第二种情况

空链表欸！是空链表欸！
直接返回NULL就好了欸！
我的老天鹅啊太快乐了。

第三种情况

我们总结的其实是第三种情况的过激版本，其实真正的第三种情况是开头是要删除的数据该怎么办。这种情况会让prev被打爆，变成一个永远瞎指的有害的废物。

想解决它也不难，如果开头是要删除的数字val，我们就把开头删掉，直到开头不是val之后再执行第一种情况的逻辑就好。
好，我们所有情况都解决了，接下来上代码：

代码

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

当然也可以把它们都写到一起，更美观一点。

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

两种写法都差不多，只要对，怎么写都可以。
（当然复杂度也是很重要的）

反转链表

给你单链表的头节点

head

，请你反转链表，并返回反转后的链表。

示例：

输入： head = [1,2,3,4,5]
输出： [5,4,3,2,1]

高端的食材往往只需要简单的烹饪，高端的题目也是，一行就可以让菜鸡大学生抱憾终身。

在经过反复的思考之后，菜鸡大学生给出了两种解法。

第一种解法

不整虚的，我们直接把箭头的指向改了不就好了？

三个指针，分别指向前中后。接着n2的下一位指向n1，然后n1n2n3分别后移，（n3是为了防止n2的指向改了之后找不到下一位），直到n2为空，遍历结束。

struct ListNode*reverseList(struct ListNode* head){if(head==NULL)returnNULL;struct ListNode* n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=head->next;while(n2){
        n2->next=n1;
  
        n1=n2;
        n2=n3;if(n3)
           n3=n3->next;}return n1;}

注：

• 需要判断链表是不是为空。
• 当n2指向最后的节点的时候n3会指向NULL，此时再将n3=n3->next;就不合适了，需要增加判断条件。

第二种解法

搞一个新链表，依次头插。
由于我的语言无法描绘这个精妙的代码，所以接下来，图很有用。

代码：

struct ListNode*reverseList(struct ListNode* head){struct ListNode* pphead=NULL;struct ListNode*newhead=head;while(newhead!=NULL){struct ListNode* next=newhead->next;
        newhead->next=pphead;
        pphead=newhead;
        newhead=next;}return pphead;}

链表的中间节点

给定一个头结点为

head

的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

这个第二个很重要，可以给我们省下一大把时间。
之后再说。

解法一

遍历，算长度，除二，再遍历。

不写了，意思懂就行。

解法二

快慢指针。
思路：一个指针一次走一格，另一个一次走两格。当快的指针遍历结束的时候，那个慢的指针刚好到中间位置。

看图我们可以发现有两种情况：一种是奇数个一种是偶数个。
奇数个正好指向中间节点，偶数个指向偏右的节点。
题目的良苦用心出来了。

注：

• 要注意奇数个和偶数个结束的条件不同。
• 要写while(fast&&fast->next)而不能写while(fast->next&&fast)否则当偶数个的时候会因为解引用NULL报错。

最后

还能说什么呢，菜就多练练。（指我）