解法一
递归思路，需要重新创建一个链表，空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1==nullptr) return pHead2;
if(pHead2==nullptr) return pHead1;
ListNode* list;
if(pHead1->val>pHead2->val){
list=pHead2;
list->next=Merge(pHead1,pHead2->next);
}
else{
list=pHead1;
list->next=Merge(pHead1->next,pHead2);
}
return list;
}
|
解法二
非递归思路,直接在两个链表上修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1==nullptr) return pHead2;
if(pHead2==nullptr) return pHead1;
ListNode* list=pHead1;
ListNode* index1=pHead1,*index2=pHead2,*pre=pHead1,*last;
if(pHead1->val>pHead2->val){
list=pHead2;
pre=index2;
index2=index2->next;
}
else index1=index1->next;
while(index1!=nullptr&&index2!=nullptr){
if(index2->val<index1->val){
last=index2->next;
pre->next=index2;
index2->next=index1;
pre=index2;
index2=last;
}
else
{
pre=index1;
index1=index1->next;
}
}
pre->next=index2;
return list;
}
|