【算法篇】--重温算法题
目录
前言【算
一、反转链表
二、合并两个有序链表
三、反转链表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;
}