AcWing 36. 合并两个排序的链表
原题链接
简单
作者:
Samuely
,
2022-12-11 20:36:41
,
所有人可见
,
阅读 205
我, 终于回忆起来链表了, 从2019年12月21号考研结束后就再也没看过链表了
虽然这个写的肯定是麻烦了
方法一:重新创建了一个新的链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode *l3 = new ListNode(-1); // 这里是搞一个指针
ListNode *h = l3, *p = l1, *q=l2;
ListNode *temp = NULL;
if (l1 == NULL && l2 != NULL) return l2;
if (l1 != NULL && l2 == NULL) return l1;
if (l1 == NULL && l2 == NULL) return NULL;
while(p && q) // p != NULL && q != NULL
{
if (p->val <= q->val)
{
h->val = p->val;
p = p->next;
h->next = new ListNode(-1);
temp = h;
h = h->next;
}
else
{
h->val = q->val;
q = q->next;
h->next = new ListNode(-1);
temp = h;
h = h->next;
}
}
if(p) temp->next = p;
if(q) temp->next = q;
return l3;
}
};
方法二:直接从两个链表上盘旋生成新链表
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode *l3 = new ListNode(-1), *t=l3;
ListNode *p = l1, *q = l2;
while(p!=NULL && q!=NULL)
{
if (p->val <= q->val)
{
// t->val = p->val; // 不用专门赋值, 又不是new了一个新节点
t->next = p;
t = t->next;
p = p->next;
}
else
{
// t->val = q->val;
t->next = q;
t = t->next;
q = q->next;
}
}
if (q!=NULL) t->next = q;
if (p!=NULL) t->next = p;
return l3->next;
}
};