数据结构 ——— 单链表oj题：合并两个升序链表

目录

题目要求

手搓两个简易链表

代码实现  

---

题目要求

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

---

手搓两个简易链表

代码演示：

struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n6);
struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n7);
struct ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n8);
struct ListNode* n9 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n9);

n1->val = 1;
n2->val = 3;
n3->val = 5;
n4->val = 7;

n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;

n5->val = 2;
n6->val = 4;
n7->val = 6;
n8->val = 8;
n9->val = 9;

n5->next = n6;
n6->next = n7;
n7->next = n8;
n8->next = n9;
n9->next = NULL;

---

代码实现 

代码演示：

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* cur = NULL;

while (list1 != NULL && list2 != NULL)
{
if (list1->val < list2->val)
{
if (cur == NULL)
{
head = cur = list1;
}
else
{
cur->next = list1;
cur = cur->next;
}

list1 = list1->next;
}
else
{
if (cur == NULL)
{
head = cur = list2;
}
else
{
cur->next = list2;
cur = cur->next;
}

list2 = list2->next;
}
}

if (list1 != NULL)
cur->next = list1;

if(list2 != NULL)
cur->next = list2;

return head;
}

代码解析：

思路是取 list1 或者 list2 中的较小值尾插到 cur 节点指针，需要注意的是 cur 节点指针的初始值是 NULL ，所有在串联 list1 或者 list2 前要先判断，当 list1 或者 list2 只要有一个走到空时，就结束循环，再判断是哪个链表没有走到空，再利用 cur 节点指针串联，最后返回 head 节点指针

代码验证：

算法的空间复杂度和时间复杂度：

while 循环执行了 N  次，且没有开辟额外的空间

算法的时间复杂度（大O渐进表示法）：O(N)

算法的空间复杂度（大O渐进表示法）：O(1) 

原文地址：https://blog.csdn.net/weixin_55341642/article/details/142676722

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！