反转单链表
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
解法：
我们可以利用链表的头插
创建一个为NULL的新节点，将原单链表的值在每次插入的前面
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*cur=head; //创建一个新节点 struct ListNode*newhead=NULL; //头插 while(cur){ struct ListNode*next=cur->next; //将cur节点的下一个节点指向新节点 cur->next=newhead; newhead=cur; cur=next; } return newhead; }
之前我们学会了复杂度，请大家计算一下上面代码的时间复杂度
大家真聪明！！！
复杂度
- 时间复杂度：O(n)O(n)O(n)，其中 nnn 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)O(1)O(1)。
移除链表元素
给你一个链表的头节点 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
输出：[]
提示：
- 列表中的节点数目在范围
[0, 104]内 1 <= Node.val <= 500 <= val <= 50
解法：
首先
我们while循环，条件为pcur->next!=NULL;每次进入就判断一次
while (pcur->next != NULL) { if (pcur->next->val == val) { struct ListNode* prev = pcur->next;//创建新节点保存，用来释放该节点 pcur->next = prev->next; free(prev); prev = NULL; } else //如果不是，就继续寻找遍历 pcur = pcur->next; }
以上我们是否就能解决问题了呢，是否有特殊情况们没有考虑到
特殊情况：
情况一：head =[] val =1
这种时候我们就要考虑头节点是否为空
if(head==NULL){ return head; }
情况二：head =[7,7,7,7] val =7
当头节点为空时，此时我们就要判断了
//头节点为目标删除的值 if(head->val==val){ head=head->next; free(pcur); pcur=NULL; pcur=head; }
此时的头节点变为头节点的下一个了，但还是为目标删除节点，所以这里就要使用到循环
while(head!=NULL&&head->val==val){ //头节点为目标删除的值 if(head->val==val){ head=head->next; free(pcur); pcur=NULL; pcur=head; } }
这样我们这些情况就考虑到了！！！
题解
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode*pcur=head; while(head!=NULL&&head->val==val){ //头节点为目标删除的值 if(head->val==val){ head=head->next; free(pcur); pcur=NULL; pcur=head; } } if(head==NULL){ return head; } while(pcur->next!=NULL){ if(pcur->next->val==val){ struct ListNode*prev=pcur->next; pcur->next=prev->next; free(prev); prev=NULL; } else pcur=pcur->next; } return head; }
返回链表的中间节点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
提示：
- 链表的结点数范围是
[1, 100] 1 <= Node.val <= 100
解法
第一种：我们可以利用数组，存放每一个值，在进行取中，数组的取中对我们来说轻而易举，这里就不展示了，希望大家自行编写
第二种：利用快慢指针，想必大家经常听到快慢指针的威名了，那就不解释了，直接上代码
struct ListNode* middleNode(struct ListNode* head) { struct ListNode * fast=head;//快指针，每次走两步 struct ListNode * slow=head;//慢指针，每次走一步 while(fast && fast->next){ //当我们了解到了快慢指针，则考虑的重点就是如何结束循环 fast = fast->next->next; slow = slow->next; } return slow; }
- struct ListNode * fast=head;//快指针，每次走两步
- struct ListNode * slow=head;//慢指针，每次走一步
注：当我们了解到了快慢指针，则考虑的重点就是如何结束循环
这里我们需要画图来解决：
长度为奇数时
此时为fast->next==NULL;
长度为偶数时
此时fast==NULL;
所以条件为两个
- 此时为fast->next==NULL;
- 此时fast==NULL;
题解
struct ListNode* middleNode(struct ListNode* head) { struct ListNode * fast=head; struct ListNode * slow=head; while(fast && fast->next){ fast = fast->next->next; slow = slow->next; } return slow; }
试着练习一下吧！！！ 
