合并两个链表(自定义位置合并与有序合并)LeetCode--OJ题详解

简介: 给两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。请你将 list1 中 下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点的位置。

自定义位置合并
问题:

给两个链表 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* head=list1;

for(int i=0;i<a-1;i++)

{
head=head->next;
}

struct ListNode* q=head->next;

for(int i=0;i<b-a+1;i++)

{
q=q->next;
}

head->next=list2;

while(list2->next!=NULL)

{
list2=list2->next;
}

list2->next=q;

return list1;

}

分析:

for(int i=0;i<a-1;i++)
{
head=head->next;
}
1
2
3
4
a-1 : 因为要是a 的话,指针就会指到被删除的那个元素身上,所以要写成a-1;

用一个for 循环来进行指针的移动。

因为 a-1 为0,所以条件不成立,直接跳出循环。

创建一个新的指针q = head->next ; 记录一下,被删除的第一个结点。

后面再进行

for(int i=0;i<b-a+1;i++)

q=q->next;
1
2
3
可以找到 被删除的最后一个结点的下一个结点。用q指针指向。

head->next=list2;
1
因为现在head指针指向就是第一个位置的结点,再进行赋值把list2赋给head->next; 所以现在就成功的把list2 链表连接上了。

while(list2->next!=NULL)
{
list2=list2->next;
}
1
2
3
4
接下来就是要连接list2链表的尾部了。

首先要能找到尾部的指针,所以用了一个while循环 ,来找到 list2 的最后一个结点。

所以

list2->next=q;
1
即可以成功的连接上list1 后面的结点。

有序合并
问题:

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

比如 现在有两个链表,如下所示

思路分析:
两个链表,有序合并。
首先新创建一个链表结点,作为头指针。

两个链表指针来比较其数据域的大小,要是相等就随便取一个结点的数据域尾插在新创的指针后面,取哪个,哪个指针指向下一个。
再进行比较。
如果不等,就把那个小的连接在新建链表的后面,然后它进行后移操作。
再进行比较。
最后当有一个链表的指针走到了最后一个位置,也就是为空了,再把另一个不为空的链表直接连接在新建的链表后面即可。

struct ListNode mergeTwoLists(struct ListNode list1, struct ListNode* list2){

struct ListNodelist3=(struct ListNode)malloc(sizeof(struct ListNode));
struct ListNode*p3=list3; // 简化一下
struct ListNode*head=list3;
while(list1!=NULL&&list2!=NULL)
{

    if (list1->val<list2->val)
    {
        p3->next=list1;
        list1=list1->next;
        p3=p3->next;
        p3->next=NULL;  //预防野指针出现
    }
    else
    {
        p3->next=list2;
        list2=list2->next;
        p3=p3->next;
        p3->next=NULL;  //预防野指针出现
    }
}

if (list1==NULL)
{

    p3->next=list2;
}
else
{
    p3->next=list1;
}
return  head->next;

}

目录
相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
34 1
|
1月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
48 0
Leetcode第21题(合并两个有序链表)
|
1月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
87 0
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
40 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
77 0
|
1月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
21 0
|
1月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
16 0
|
1月前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
12 0
|
1月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
29 0