合并两个有序链表
link.
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列
思路，我们可以取节点下来尾插，取两节点中的较小的值尾插在新节点里面，我们同时可以弄一个哨兵位的头节点，尾插的时候，我们还可以定义一个尾指针，指向链表的尾部
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1==NULL)//如果list1为空的话，就返回list2，无论list2是否为空都是符合的
{
return list2;
}
if(list2==NULL)//同理
{
return list1;
}
struct ListNode*head=NULL;//一开始初始化新头和尾都是NULL
struct ListNode*tail=NULL,*n1=list1,*n2=list2;
//1.没有带哨兵位的头节点
/*if(n1->val<=n2->val)
{
head=tail=n1;
n1=n1->next;
}
//这就是把里面判断头为空给跳过去了
else
{
head=tail=n2;
n2=n2->next;
}*/
//带哨兵位的头
//head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//返回的时候是head->next;再free掉
while(n1&&n2)
{
if(n1->val<=n2->val)
{
if(head==NULL)//如果新链表没有节点，就把第一个节点头和尾都为n1
{
head=tail=n1;
}
else
{
tail->next=n1;//tail指向n1部分
tail=n1;//再把tail更新一下
}
n1=n1->next;
}
else//同理
{
if(head==NULL)
{
head=tail=n2;
}
else
{
tail->next=n2;
tail=n2;
}
n2=n2->next;
}
}
if(n1)//如果n1不为空，那么就把n1整个链接到tail的后面
{
tail->next=n1;
}
else
{
tail->next=n2;
}
return head;//返回头
}
移除链表元素
link.
给你一个链表的头节点 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 <= 50 0 <= val <= 50
思路
弄一个新链表，如果不为val就把原链表的节点链接到新链表里面去
为val就跳过去
struct ListNode* removeElements(struct ListNode* head, int val){
if(head==NULL)
{
return NULL;
}
//新定义一个头节点，尾节点
struct ListNode*newhead=NULL,*tail=NULL,*cur=head;
while(cur!=NULL)
{
if(cur->val!=val)//不为val
{
if(newhead==NULL)
{
newhead=tail=cur;
}
else
{
tail->next=cur;
tail=cur;
}
cur=cur->next;
}
else//为val
{
cur=cur->next;
}
}
//[7,6,7,7] val=7
//新链表是[6,7,7],后面也会一起链接进去，所以我们要处理后面的val，而且后面全是val，prev指向l的下一个
struct ListNode*l=newhead;
struct ListNode*prev=NULL;//prev是l的前驱
while(l)
{
if(l->val!=val)
{
prev=l;
l=l->next;
}
else
{
prev->next=l->next;//prev指向后一个，跳过那个点
free(l);//释放掉
l=prev->next;l跳到prev的后一个，这个时候prev的后一个已经被改变了
}
}
return newhead;
}
分割链表
link.
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你不需要 保留 每个分区中各节点的初始相对位置
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内 -100 <= Node.val <= 100 -200 <= x <= 200
思路
我们可以弄两个链表，一个链表是小于x的链表，一个是大于等于x的链表
后面把两个链表链接起来，循环后面都指向NULL，把后面都截断掉，避免还有链接
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode*lesshead=NULL,*lesstail=NULL,*morehead=NULL,*moretail=NULL,*cur=head;
lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
//
morehead=moretail=(struct ListNode*)malloc(sizeof(struct ListNode));
while(cur)
{
if(cur->val<x)//小于x的链接起来
{
lesstail->next=cur;
lesstail=cur;
cur=cur->next;
}
else//大于x的链接起来
{
moretail->next=cur;
moretail=cur;
cur=cur->next;
}
}
lesstail->next=NULL;//吧tail后面都置成空哦
moretail->next=NULL;
lesstail->next=morehead->next;//再连接起来
struct ListNode*new=lesshead->next;
free(morehead);
free(lesshead);
morehead=lesshead=NULL;
return new;
}