09/25 17:21

# 我的题解

最开始，我的思路是最简单的思路，就是再新申请空间，遍历两个链表。最后拼装成结果。

``````class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* rp = &dummy;
while(l1!=NULL&&l2!=NULL) {
int val1 = l1->val;
int val2 = l2->val;
int val = val2;
if(val1<=val2) {
val = val1;
l1 = l1->next;
} else {
l2 = l2->next;
}
ListNode* np = new ListNode(val);
rp->next = np;
rp=np;
}
while(l1!=NULL) {
ListNode* np = new ListNode(l1->val);
rp->next = np;
rp=np;
l1=l1->next;
}
while(l2!=NULL) {
ListNode* np = new ListNode(l2->val);
rp->next = np;
rp=np;
l2=l2->next;
}
return dummy.next;
}
};
``````

看到打败的人数很低，我稍作思考，我认为可以借助其中一个链表来做这件事，但是时间消耗还是不理想。

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL&&l2==NULL) {
return l1;
}
if(l1==NULL) {
return l2;
}
if(l2==NULL) {
return l1;
}

ListNode* otherList = l2;
ListNode* last = new ListNode(0);
ListNode* resultDummyNode = last;

if(l1->val>l2->val){
otherList = l1;
}

}
last = last->next;
otherList= otherList->next;
}
}
while(otherList!=NULL) {
last->next = new ListNode(otherList->val);
otherList = otherList->next;
last = last->next;
}
return resultDummyNode->next;
}
};
``````

# 官方题解

``````class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};

``````

1
2 收藏

09/26 17:36

2 评论
2 收藏
1