文章目录
合并两个有序链表
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; }
