做网站要花多少钱,中国咨询公司,东莞网站建制作,网站布局类型图片: csdn
自定义位置合并
问题#xff1a;
给两个链表 list1 和 list2 #xff0c;它们包含的元素分别为 n 个和 m 个。
请你将 list1 中 下标从 a 到 b 的全部节点都删除#xff0c;并将list2 接在被删除节点
的位置。
比如#xff1a; 输入#xff1a;list1 [1…图片: csdn
自定义位置合并
问题
给两个链表 list1 和 list2 它们包含的元素分别为 n 个和 m 个。
请你将 list1 中 下标从 a 到 b 的全部节点都删除并将list2 接在被删除节点
的位置。
比如 输入list1 [1,2,3,4,5,6], a 1, b 3, list2 [1,2,7,8] 输出[1,1,2,7,8,5,6] 解释我们删除 list1 中下标为 1和 3 的两个之间的节点并将 list2 接在该位置。 如图中用红线所连接的即是最后所求。
代码 /** Definition for singly-linked list. struct ListNode { int val; struct ListNode *next; } ** /
struct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2)
{struct ListNode* headlist1;for(int i0;ia-1;i){
headhead-next;
}struct ListNode* qhead-next;for(int i0;ib-a1;i){
qq-next;
}head-nextlist2;while(list2-next!NULL){
list2list2-next;
}list2-nextq;return list1;}分析
for(int i0;ia-1;i)
{
headhead-next;
}a-1 因为要是a 的话指针就会指到被删除的那个元素身上所以要写成a-1
用一个for 循环来进行指针的移动。
因为 a-1 为0所以条件不成立直接跳出循环。
创建一个新的指针q head-next ; 记录一下被删除的第一个结点。
后面再进行 for(int i0;ib-a1;i)qq-next;可以找到 被删除的最后一个结点的下一个结点。用q指针指向。
head-nextlist2;因为现在head指针指向就是第一个位置的结点再进行赋值把list2赋给head-next 所以现在就成功的把list2 链表连接上了。
while(list2-next!NULL)
{
list2list2-next;
}接下来就是要连接list2链表的尾部了。
首先要能找到尾部的指针所以用了一个while循环 来找到 list2 的最后一个结点。
所以
list2-nextq;即可以成功的连接上list1 后面的结点。
有序合并
问题
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的 两个链表的所有节点组成的。
比如 现在有两个链表如下所示 思路分析 两个链表有序合并。 首先新创建一个链表结点作为头指针。
两个链表指针来比较其数据域的大小要是相等就随便取一个结点的数据域尾插在新创的指针后面取哪个哪个指针指向下一个。 再进行比较。 如果不等就把那个小的连接在新建链表的后面然后它进行后移操作。 再进行比较。 最后当有一个链表的指针走到了最后一个位置也就是为空了再把另一个不为空的链表直接连接在新建的链表后面即可。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode*list3(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*p3list3; // 简化一下struct ListNode*headlist3;while(list1!NULLlist2!NULL){if (list1-vallist2-val){p3-nextlist1;list1list1-next;p3p3-next;p3-nextNULL; //预防野指针出现}else{p3-nextlist2;list2list2-next;p3p3-next;p3-nextNULL; //预防野指针出现}}
if (list1NULL)
{p3-nextlist2;}else{p3-nextlist1;}return head-next;
}
