ListNode* mergeTwoLists-链接
实现的代码如下：
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *a=l1;
ListNode *b=l2;
//考虑l1链表为空，l2链表不为空的情况；
if(l1==NULL)
{
while(l2!=NULL)
{
addelem(l2->val);
l2=l2->next;
}
}
//考虑l2链表为空，l1链表不为空的情况;
if(l2==NULL)
{
while(l1!=NULL)
{
addelem(l1->val);
l1=l1->next;
}
}
//分治
while((a!=NULL&&b!=NULL)){
if (a->val >= b->val) {
addelem(b->val);
b = b->next;
} else {
addelem(a->val);
a = a->next;
}
while(a==NULL&&b!=NULL)
{
addelem(b->val);
b=b->next;
}
while(a!=NULL&&b==NULL)
{
addelem(a->val);
a=a->next;
}
}
return head->next;
}
private:
ListNode *head=new ListNode(0);
ListNode *p=head;
void addelem(int elem)
{
cout<<elem<<endl;
ListNode *node=new ListNode(elem);
p->next=node;
p=node;
}
};
|
虽然我这的这个代码AC了，可是比较冗杂…..
接下来，就要对上述代码进行简化
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* head = new ListNode(0);
ListNode* p = head;
ListNode* a = l1;
ListNode* b = l2;
//和上面一样，分治，不过这里直接进行元素的添加了，没有另外再调用函数，利用一个头结点的指针p
while(a != NULL && b != NULL){
if(a->val < b->val){
p->next = a;
a = a->next;
}
else{
p->next = b;
b = b->next;
}
p = p->next;
}
//比如a为空了但是b不为空，虽然跳出了while循环，但是还有元素没有存入到头链表中去，直接把整个没有空的链表接到p->next后面
if(a != NULL)
p->next = a;
else
p->next = b;
//我们最后返回的应该是头结点的后面的那个节点
ListNode* ret = head->next;
head->next = NULL;
//删掉头节点
delete head;
return ret;
}
};
|
简化后的代码与刚开始的那个思想有点不一样，不过最重要的都是采取了分治的做法来完成的
