您现在的位置是:首页 >学无止境 >合并两个有序链表网站首页学无止境
合并两个有序链表
简介合并两个有序链表
1.题目描述
题目链接:力扣21,合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
2.解题思路
方法1:
首先我们能够想到的就是遍历一遍数组,判断两个结点的大小,将数值小的结点放在前面,数值大的不断尾插在后面。是不是听着挺简单的?
具体实现:
我们可以创建两个空指针,head用来存放链表的头结点,tail用来遍历两条链表,将两条链表链接起来。
- 当某个链表为空时,我们可以直接返回另一条链表
- 当两个链表都不为空时,我们可以不断比较两条链表的大小,当 head 和 tail 为空时,我们将较小的结点同时赋给 head 和 tail。然后就是比较两条list的大小,将tail指向较小的结点,并将 tail 移到它的下一个结点位置。同时也将 list 指向它的下一个结点。
- 当一条链表遍历完后,由于链表是链接起来的,我们可以直接将尾指针 tail 指向另一条链表。这样两条链表就链接起来了。
- 最后我们再返回头结点 head 就可以了。
上代码:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
struct ListNode* head=NULL;
struct ListNode* tail=NULL;
while(list1 && list2)
{
if(list1->val < list2->val)
{
if(head == NULL)
{
head = list1;
tail = head;
list1 = list1->next;
}
else
{
tail->next = list1;
list1 = list1->next;
tail = tail->next;
}
}
else
{
if(head == NULL)
{
head = list2;
tail = head;
list2 = list2->next;
}
else
{
tail->next = list2;
list2 = list2->next;
tail = tail->next;
}
}
if(list1)
tail->next=list1;
else
tail->next=list2;
}
return head;
}
方法2:
- 方法二和方法一差不多,我们可以创建一个带哨兵位的头结点,将小的结点不断尾插到这个带哨兵位的头节点后面,这样我们就不用判断链表是不是空链表了。
- 所谓带哨兵位的链表,就是一个附加的链表的节点,该节点作为第一个节点,它的值域并不存储任何东西,只是为了操作的方便引用的。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* f1=list1;
struct ListNode* f2=list2;
struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* f3=head;
while(f1 && f2)
{
if(f1->val < f2->val)
{
f3->next=f1;
f1=f1->next;
}
else
{
f3->next=f2;
f2=f2->next;
}
f3=f3->next;
f3->next=NULL;
}
if(f2==NULL)
{
f3->next=f1;
}
else
{
f3->next=f2;
}
return head->next;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。