目录
前言【算
一、反转链表
二、合并两个有序链表
三、反转链表II
四、移除链表元素
前言
本篇文章基于学习了一段数据结构，并练习了几道算法题所做的一些笔记，方便日后复习时可以用到。
如果有什么不对的地方，欢迎大家在评论区指正；
一、反转链表
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
对于这道题，我们只需将原来指向下一位节点反转过来即可，也就是说让5指向4，4再指向3，最后指向1，首先定义三个指针，n1,n2,n3, n2对应头节点，n3指向n2的下一个位置（即n3=n2->next)，依次循环遍历，让n2->next指向n1，继续向后移动，n1移动到原来n2位置，n2移动到n3位置，n3继续向前走，直至不为空时结束
图片展示：
代码展示：
struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){if(head==NULL){return head;}ListNode *n1,*n2,*n3;n1=NULL,n2=head,n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}二、合并两个有序链表
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
此方法来源一题解网友，在这里主要回顾一下。
首先我们创建新的链表来实现，前面要判断，如果其中一个为空，则返回另一个链表。然后while循环遍历，判断n1 n2指向的list1 list2的头节点哪个小，小的进行尾插，尾插到新链表的后面（即就是让newtail->next指向小的那个）， 这里的（n1 && n2）意思是一个为空，则跳出循环，最后记得销毁newhead，并返回newhead->next
代码块：
struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode* n1=list1;ListNode* n2=list2;//创建新链表ListNode* newhead;ListNode* newtail;newhead=newtail=(ListNode*)malloc(sizeof(ListNode));if(list1==NULL){return list2;}if(list2==NULL){return list1;}while(n1 && n2){if(n1->val>=n2->val){newtail->next=n2;n2=n2->next;}else{newtail->next=n1;n1=n1->next;}newtail=newtail->next;}//跳出循环,如果n1先走到空，将n2剩余节点连接到表尾if(n2){newtail->next=n2;}else{newtail->next=n1;}ListNode* ret=newhead->next;free(newhead);newhead=NULL;return ret;
}三、反转链表II
题目描述：
给你单链表的头指针
head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回 反转后的链表 。
这道题的整体思想如同官方第二种解法：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。什么意思呢，按示例1来说，2是left,4是right,在2和4区间里(也就是left 和right区间里），走到3这个位置的话，让3这个位置插入到2的前面，再走到4这块，让4插入到3的前面，依次这样，就能实现left和right位置的反转，示例1由于中间较少，可能不好理解，下面这张图更能加深理解。
操作步骤：
先在left（也就是图中的curr)前一位置定义一个pre,再定义个next，让他等于left下一位，执行如下图的操作1，curr->next指向next->next,再让next->next指向pre->next（操作2）,最后让pre->next指向next（操作3）。这样就完成了。
代码演示：
struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {ListNode* dump=(ListNode*)malloc(sizeof(ListNode));dump->val=-1;dump->next=head;ListNode* pre=dump;//持续遍历pre，使得它到left前一个位置for(int i=0;i<left-1;i++){pre=pre->next;}ListNode* cur=pre->next;ListNode* next;for(int i=0;i<right-left;i++){next=cur->next;cur->next=next->next;next->next=pre->next;pre->next=next;}return dump->next;
}四、移除链表元素
题目描述：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
题目要求移除满足条件的节点并删除，返回一个新的头节点。那我们逆向走，我们创建一个新的链表，让不满足
Node.val == val的节点到新的链表去，这样也实现了删除的作用。首先我们创建一个pcur指针，指向的是原链表的头节点，然后while循环遍历，pcur不为空，再进行if判断即可。循环结束后newtail不为空的话，让他的下一位滞空，防止出现野指针，最后返回新的链表头节点即可。
代码展示：
struct ListNode {* int val; //int data;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//创建一个空链表ListNode *newhead,*newtail;newhead=newtail=NULL;ListNode *pcur=head;while(pcur){//找值不为val的节点if(pcur->val!=val){if(newtail==NULL){newhead=newtail=pcur;}else{newtail->next=pcur;newtail=newtail->next;}}pcur=pcur->next;}if(newtail){newtail->next=NULL;}return newhead;
}
