反转单链表
给定单链表的头节点 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;
} 试着练习一下吧！！！