题目:Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
简单题,只要对两个链表中的元素进行比较,然后移动即可,只要对链表的增删操作熟悉,几分钟就可以写出来,代码如下:
1 struct ListNode {
2 int val;
3 ListNode *next;
4 ListNode(int x):val(x), next(NULL) {}
5 };
6
7 ListNode *GetLists(int n) //得到一个列表
8 {
9 ListNode *l = new ListNode(0);
10 ListNode *pre = l;
11 int val;
12 for (int i = 0; i < n; i ++) {
13 cin >> val;
14 ListNode *newNode = new ListNode(val);
15 pre->next = newNode;
16 pre = pre->next;
17 }
18 return l->next;
19 }
20
21 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
22 {
23 assert (NULL != l1 && NULL != l2);
24 if (NULL == l1 && NULL == l2)
25 return NULL;
26 if (NULL == l1 && NULL != l2) // !!要记得处理一个为空,另一个不为空的情况
27 return l2;
28 if (NULL != l1 && NULL == l2)
29 return l1;
30
31 ListNode *temp = new ListNode(0);
32 temp->next = l1;
33 ListNode *pre = temp;
34
35 while(NULL != l1 && NULL != l2) {
36 if (l1->val > l2->val) { //从小到大排列
37 ListNode *next = l2->next;
38 l2->next = pre->next;
39 pre->next = l2;
40 l2 = next;
41 }
42 else {
43 l1 = l1->next;
44 }
45 pre = pre->next;
46 }
47 if (NULL != l2) {
48 pre->next = l2;
49 }
50 return temp->next;
51 }
这其中要注意一点,即要记得处理一个链表为空,另一个不为空的情况,如{}, {0} -- > {0},当然上面的写法多少啰嗦了一些,可以简写。