单链表经典算法

算法"/>

单链表经典算法

移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：（1）创建三个结构体指针，分别代表一条新链表的头newhead，一条新链表的尾newtail，还有一个用于循环旧链表的pcur
（2）循环旧链表，当pcur的val不等于函数参数中的val时：1.当新链表为空时，将新链表的newhead和newtail赋值为pcur 2.当新链表不为空时，newtail的next指向pcur，newtail赋值为newtial的next；
（3）运行完一个结点pcur赋值为pcur的next
（4）当运行结束时，代表旧链表运行完毕，当最后一个结点等于val时，newtail的值不会是空，而是旧链表最后一个结点的值，因此我们需要进行判断，当newtail不为空时，需要将newtail置空，最后返回newhead即可

struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* newhead=NULL;struct ListNode* newtail=NULL;struct ListNode* pcur=head;while(pcur){if(pcur->val != val){if(newhead == NULL){newhead=newtail=pcur;}else{newtail->next=pcur;newtail=newtail->next;}}pcur=pcur->next;}if(newtail){newtail->next=NULL;}return newhead;
}

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：（1）若链表为空，则直接返回空
（2）若不为空，创建三个结构体指针分别为n1,n2,n3，将n1赋值为NULL，n2赋值为head，n3赋值为head->next
（3）以n2为循环条件进行遍历，每次运行都将n2的next赋值为n1，n1赋值为n2，n2赋值为n3，若n3不为空则n3赋值为n3的next（下图为第一次和第二次循环图）
（4）又因为n2和n3最后的位置都为NULL，所以最后返回n1即可。

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

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：（1）判断传入的参数list1、list2是否为空，为空则返回另一个
（2）创建四个结构体指针，newhead代表新链表的头，newtail代表新链表的尾，pcur1和pcur2分别用来遍历list1和list2
（3）若pcur1和pcur2都不为空则进入循环，当pcur1的val大于pcur2的val，判断newhead是否为空，为空则将newhead和newtail赋值为pcur1，不为空则进行新链表结点的插入，即将newtail的next赋值为pcur1，newtail赋值为newtail的next；pcur1小于等于pcur2时同理，只需将pcur1改为pcur2即可
（4）当循环结束，判断pcur1与pcur2是否为空，某个不为空时，将newtail的next赋值为不为空的pcur，最后返回newhead即可

• 不带头单向不循环链表

//不带头单向不循环链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}struct ListNode* newhead=NULL;struct ListNode* newtail=NULL;struct ListNode* pcur1=list1;struct ListNode* pcur2=list2;while(pcur1 && pcur2){if((pcur1->val) < (pcur2->val)){if(newhead == NULL){newhead=newtail=pcur1;}else{newtail->next=pcur1;newtail=newtail->next;}pcur1=pcur1->next;}else{if(newhead == NULL){newhead=newtail=pcur2;}else{newtail->next=pcur2;newtail=newtail->next;}pcur2=pcur2->next;}}if(pcur1 != NULL){newtail->next=pcur1;}    if(pcur2 != NULL){newtail->next=pcur2;}return newhead;
}

• 带头单向不循环链表
  思路：（1）newhead和newtail的初始值不再是NULL，而是一个没有val值的结点，相当于是一个哨兵位。因此就不再需要判断newhead是否为空。
  （2）最后需要将malloc的newhead指针释放，需要创捷一个新结构体指针rehead赋值为newhead的next，便可进行newhead的释放，最后返回rehead即可

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* newtail=newhead;struct ListNode* pcur1=list1;struct ListNode* pcur2=list2;while(pcur1 && pcur2){if((pcur1->val) < (pcur2->val)){newtail->next=pcur1;newtail=newtail->next;pcur1=pcur1->next;}else{newtail->next=pcur2;newtail=newtail->next;pcur2=pcur2->next;}}if(pcur1 != NULL){newtail->next=pcur1;}    if(pcur2 != NULL){newtail->next=pcur2;}struct ListNode* rehead=newhead->next;free(newhead);newhead=NULL;return rehead;
}

链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

思路：（1）运用快慢指针，创建两个结构体指针，分别为slow和fast，slow每次走一个结点，fast每次走两个结点（如下图）
（2）返回slow指针即可

struct ListNode* middleNode(struct ListNode* head) 
{struct ListNode* fast=head;struct ListNode* slow=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}