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 };