1. 反轉(zhuǎn)鏈表（206）

1.1 題目描述

1.2 題目分析

1.2.1 頭插法

要將原來的鏈表進(jìn)行反轉(zhuǎn)，很容易想到，將原來的節(jié)點(diǎn)取下來，然后一個(gè)一個(gè)進(jìn)行頭插到新鏈表中struct ListNode* newhead=NULL。
原鏈表中，如果cur不為空，那么cur->next=newhead,再將newhead置為新鏈表的頭節(jié)點(diǎn)。
為了方便記錄原鏈表節(jié)點(diǎn)的位置，在原鏈表上定義一個(gè)struct ListNode* next=cur->next。

如果cur為空，這里就需要一個(gè)新的鏈表，所以最后不要忘記返回新鏈表的頭節(jié)點(diǎn)。

1.2.2 箭頭反轉(zhuǎn)

還有一種方法就是將這些節(jié)點(diǎn)的箭頭反向，也就是將后一個(gè)節(jié)點(diǎn)的next等于前一個(gè)節(jié)點(diǎn)。

反轉(zhuǎn)之后就是這樣:

也就是說：先定義兩個(gè)指針，先將n1置為空，然后n2指向頭節(jié)點(diǎn)，再將n2->next=n1。然后繼續(xù)往后走，需要記錄n2后一個(gè)節(jié)點(diǎn)位置，再定義一個(gè)n3=head->next,只要鏈表不為空，就讓 n2->next=n1;n1=n2;n2=n3。
但是在最后一步n3可能為空，所以得加一個(gè)判斷，為空就不往后執(zhí)行了。
最值得注意的一點(diǎn)是，如果原鏈表為空，那么后面都不執(zhí)行，所以開始得加一個(gè)判斷

    if(head==NULL){return NULL;}

1.3 題目代碼

1.3.1 頭插入

struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

1.3.2 箭頭反轉(zhuǎn)

struct ListNode* reverseList(struct ListNode* head){if(head==NULL){return NULL;}struct ListNode* n1,*n2,*n3;n1=NULL;n2=head;n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}

2.合并兩個(gè)有序鏈表（21）

2.1 題目描述

2.2 題目分析

題目要求是按照升序返回合并的原來排好序的兩個(gè)鏈表，這里就可以用尾插，比較兩個(gè)鏈表節(jié)點(diǎn)的val，對(duì)比一下，取小的進(jìn)行尾插。

這里肯定要事先判斷一下這兩個(gè)鏈表是不是為空：如果鏈表1為空，就直接返回鏈表2。同樣，鏈表2為空，就返回鏈表1。

      if(list1==NULL){return list2;}if(list2==NULL){return list1;}

在已有的鏈表上面經(jīng)行插入比較繁瑣，就直接用一個(gè)新的，最后返回排好鏈表的頭節(jié)點(diǎn)就行。
只有兩個(gè)鏈表都不為空時(shí)，再考慮是鏈表1節(jié)點(diǎn)的val與鏈表2的val：如果 list1->val< list2->val，還是得判斷一下這個(gè)新鏈表里面有沒有節(jié)點(diǎn)：沒有就直接讓head=tail=list1，有就實(shí)現(xiàn)尾插。

           if(tail==NULL){head=tail=list1;}else{tail->next=list1;tail=tail->next;}

然后鏈表1繼續(xù)往后走。
但是如果 list1->val< list2->val是錯(cuò)誤的，那么鏈表2也是同樣的：

           if (tail == NULL){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;

當(dāng)一個(gè)鏈表已經(jīng)排好了，如果剩下的是鏈表1，就直接插入

       if(list1){tail->next=list1;}

如果剩下的是鏈表2，就直接插入：

       if(list2){tail->next=list2;}

最后別忘記返回頭節(jié)點(diǎn)。

2.3 題目代碼

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* head=NULL;struct ListNode* tail=NULL;while(list1&&list2){if(list1->val<list2->val){if(tail==NULL){head=tail=list1;}else{tail->next=list1;tail=tail->next;}list1=list1->next;}else{if(tail==NULL){head=tail=list2;}else{tail->next=list2;tail=tail->next;}list2=list2->next;}}if(list1){tail->next=list1;}if(list2){tail->next=list2;}return head;}