來(lái)源：左程云算法

鏈表的題目我們經(jīng)常是有思路但是實(shí)現(xiàn)起來(lái)總有些小問(wèn)題，所以是準(zhǔn)備筆試應(yīng)多加練習(xí)的一類題

206. 反轉(zhuǎn)鏈表

這道題我們可以新開鏈表來(lái)存，但是如果面試中有這道題，面試官讓你優(yōu)化又該如何呢？所以我們采用前后指針?lè)椒▉?lái)解決

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *pre=nullptr;//前指針ListNode *next=nullptr;//后指針while(head){ next=head->next;//先把該節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)存下來(lái)head->next=pre;//修改該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為前一結(jié)點(diǎn)pre=head;//前一結(jié)點(diǎn)移到當(dāng)前位置head=next;//當(dāng)前結(jié)點(diǎn)往后移動(dòng)}return pre;//最后pre保存新的頭結(jié)點(diǎn)，另兩個(gè)結(jié)點(diǎn)為空}
};

同時(shí)，本題還有遞歸解法，非常巧妙

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==nullptr||head->next==nullptr)return head;//第一個(gè)條件只是判斷初始鏈表為空的情況ListNode *cur=reverseList(head->next);//以[1,2,3,4,5]為例，現(xiàn)在head指向4，cur指向5head->next->next=head;//head->next指向反轉(zhuǎn)鏈表的最后一個(gè)，此句把自己接到后面head->next=nullptr;//接到的是尾部，所以next為nullptrreturn cur;}
};

附錄：反轉(zhuǎn)雙鏈表

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* next = nullptr;while (head ) {next = head->next;head->next = pre;head->last = next;pre = head;head = next;}return pre;}

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

這里我們使用一個(gè)哨兵結(jié)點(diǎn)方便后續(xù)書寫

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode head{};//哨兵結(jié)點(diǎn)ListNode* cur=&head;//指向哨兵結(jié)點(diǎn)while(list1&&list2){if(list1->val<list2->val){cur->next=list1;//指向小的list1=list1->next;//鏈表指針移動(dòng)}else{cur->next=list2;list2=list2->next;}cur=cur->next;//合并鏈表指針移動(dòng)到尾結(jié)點(diǎn)}cur->next=list1?list1:list2;//哪個(gè)有剩余就加上return head.next;//返回頭節(jié)點(diǎn)}
};

2. 兩數(shù)相加

這道題依然使用哨兵結(jié)點(diǎn)，便于處理

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int up = 0;//算進(jìn)位和余數(shù)ListNode* head = new ListNode;//哨兵結(jié)點(diǎn)ListNode* cur = head;//指針指向哨兵結(jié)點(diǎn)while (l1 || l2 || up) {//只要鏈表沒(méi)遍歷完，或進(jìn)位里仍有數(shù)int val1 = l1 ? l1->val : 0;//鏈表不為空取值int val2 = l2 ? l2->val : 0;up += val1 + val2;//之前進(jìn)上的位與當(dāng)前相加ListNode* t = new ListNode(up % 10);//新建結(jié)點(diǎn)存答案up /= 10;//應(yīng)進(jìn)位多少cur->next = t;//接到答案鏈表后面cur = cur->next;//鏈表指針移動(dòng)if (l1)l1 = l1->next; //鏈表不為空移動(dòng)if (l2)l2 = l2->next;}return head->next;//返回哨兵結(jié)點(diǎn)保存的頭結(jié)點(diǎn)}
};

86. 分隔鏈表

這個(gè)題如果我們掃描然后把小的放前面用到的指針比較多，較麻煩。

所以我們用兩個(gè)鏈表分別存儲(chǔ)，再最后合并即可。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* partition(ListNode* head, int x) {//開兩個(gè)鏈表分別存儲(chǔ)，最后合并鏈表即可ListNode* lower = new ListNode(0);//<x的結(jié)點(diǎn)ListNode* upper = new ListNode(0);//>=x的結(jié)點(diǎn)//兩個(gè)都是哨兵結(jié)點(diǎn)ListNode *p1 = lower, *p2 = upper;//指針?lè)謩e指向兩鏈表，便于后續(xù)增加結(jié)點(diǎn)if (!head)return head;//為空直接返回while (head) {//一直遍歷if (head->val < x) {//小于接到lower鏈表p1->next = head;p1 = p1->next;head = head->next;} else {p2->next = head;//大于等于接到upper鏈表p2 = p2->next;head = head->next;}}p1->next = upper->next;//upper接到lower后面p2->next = nullptr;//尾部置nullreturn lower->next;}
};