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、常规边界判定
2、由于最终要返回合成的链表头部,因此需要先比较l1和l2首个结点值大小,确定ret值;
3、新建一个cur指针操作要返回的链表,串起l1和l2;
记录:
1、指针赋值的关注点在等号的右边。指针名是变量名,随着赋值操作随时改变,不会产生连带影响;
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
12 ListNode *ret = NULL;
13 ListNode *cur = NULL;
14
15 if (!l1) return l2;
16 if (!l2) return l1;
17
18 if (l1->val <= l2->val) {
19 ret = l1;
20 l1 = l1->next;
21 } else {
22 ret = l2;
23 l2 = l2->next;
24 }
25
26 cur = ret;
27 while (l1 && l2) {
28 if (l1->val <= l2->val) {
29 cur->next = l1;
30 l1 = l1->next;
31 } else {
32 cur->next = l2;
33 l2 = l2->next;
34 }
35 cur = cur->next;
36 }
37
38 if (!l1)
39 cur->next = l2;
40 else
41 cur->next = l1;
42
43 return ret;
44 }
45 };
文艺做法:
使用二重指针解决了判定链表头大小的步骤
类似另一道简单题Remove Nth Node From End of List
Linus once said " People who understand pointers just use a“pointer to the entry pointer”"
1 class Solution {
2 public:
3 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
4 ListNode* head = NULL, **t = &head;
5 while(l1 != NULL && l2 != NULL) {
6 if(l1->val < l2->val) {
7 *t = l1;
8 l1 = l1->next;
9 } else {
10 *t = l2;
11 l2 = l2->next;
12 }
13 t = &((*t)->next);
14 }
15 *t = (l1 != NULL ? l1 : l2);
16 return head;
17 }
18 };