LeetCode-鏈表
鏈表（Linked List）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)蔬充，是一種線性表碳胳，但是并不會按線性的順序存儲數(shù)據(jù)运嗜，而是在每一個節(jié)點里存到下一個節(jié)點的指針（Pointer）晕城。
由于不必須按順序存儲，鏈表在插入的時候可以達(dá)到 O(1)O(1) 的復(fù)雜度橡羞，比另一種線性表 —— 順序表快得多愕贡，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要 O(n)O(n) 的時間创南，而順序表相應(yīng)的時間復(fù)雜度分別是 O(log\ n)O(log n) 和 O(1)O(1)。
對于鏈表相關(guān)的問題我擂，應(yīng)該注意以下幾點：
頭節(jié)點的使用衬以，即dummyNode的使用缓艳，可以減少邊界條件判斷校摩。涉及到頭節(jié)點的操作看峻，比如可能刪除head等等，使用dummyNode可以減少判斷衙吩。最后返回dummyNode.next
創(chuàng)建新的節(jié)點時互妓，注意在棧上分配對象，如果使用new 需要delete坤塞。ps：后續(xù)一些題解沒有及時更正該方面的問題冯勉。
-
快慢指針。多用于尋找中間節(jié)點等摹芙，衍生問題環(huán)形鏈表等灼狰。主要在于在O(N)的時間來快速獲取到想要的節(jié)點。
使用快慢指針查找中間節(jié)點時浮禾，當(dāng)fast和slow都指向head和slow指向head交胚，fast指向head->next 獲取到的中間節(jié)點及邊界條件不一致，需要注意盈电。
cut函數(shù)蝴簇，cut(ListNode* node,int k) 將鏈表前k個值切割，返回第k+1個node匆帚；多用于分隔鏈表熬词。
反轉(zhuǎn)鏈表，需要pre=null,cur=head,next 三個指針吸重， 每次進(jìn)行更新互拾，最后返回pre。
合并鏈表嚎幸，注意dummyNode的使用以及邊界判空摩幔。
刪除節(jié)點，刪除當(dāng)前節(jié)點鞭铆，可以將下個節(jié)點的值復(fù)制給當(dāng)前節(jié)點或衡，并指向下下個節(jié)點。另一種思路時需要找到刪除節(jié)點的前驅(qū)车遂。
時間復(fù)雜度封断，可以考慮一些輔助工作，如map舶担，stack坡疼，set等。
另一個就是鏈表和排序算法以及樹的遍歷的結(jié)合衣陶。歸并排序柄瑰，dfs等等闸氮。可以等后續(xù)章節(jié)進(jìn)行分析教沾。
鏈表相關(guān)的問題也可以考慮遞歸的方式進(jìn)行解決蒲跨。從而簡化問題。
下面介紹LeetCode常見的鏈表問題授翻。
1.反轉(zhuǎn)鏈表
206.反轉(zhuǎn)鏈表或悲。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head==NULL || head->next==NULL){
return head;
}
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* next;
while(cur){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
92.反轉(zhuǎn)鏈表II
反轉(zhuǎn)從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉(zhuǎn)堪唐。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head==NULL || head->next==NULL){
return head;
}
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* next;
while(m>1){
pre=cur;
cur=cur->next;
m--;
n--;
}
// 需要記錄下pre 和 tail巡语；即反轉(zhuǎn)后的頭節(jié)點和尾節(jié)點
ListNode* con = pre; //反轉(zhuǎn)后的頭節(jié)點
ListNode* tail=cur; // 反轉(zhuǎn)后的尾節(jié)點
while(n>0){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
n--;
}
if(con){
con->next=pre; //進(jìn)行連接
}else{
head=pre; //此時證明從第一個節(jié)點開始反轉(zhuǎn)，那么頭節(jié)點直接就是反轉(zhuǎn)后的頭節(jié)點
}
tail->next=cur; //尾節(jié)點的next設(shè)置為下一個節(jié)點cur
return head;
}
};
2.刪除元素
237.刪除鏈表中的節(jié)點
class Solution {
public:
void deleteNode(ListNode* node) {
//struct ListNode* tmp=node->next;
node->val=node->next->val;
node->next=node->next->next;
//delete tmp;
}
};
203.移除鏈表元素
刪除鏈表中等于給定值 *val* 的所有節(jié)點淮菠。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(head==NULL){
return NULL;
}
struct ListNode* t=new ListNode(-1);
t->next=head;
struct ListNode* pre=t;
while(pre->next!=NULL){
if (pre->next->val==val){
auto s=pre->next;
pre->next=pre->next->next;
delete s;
}else{
pre=pre->next;
}
}
return t->next;
}
};
19.刪除鏈表的倒數(shù)第N個節(jié)點
給定一個鏈表男公，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點合陵。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head==NULL || head->next==NULL){
return NULL;
}
ListNode* first=head;
ListNode* second=head;
int i=0;
// 先走n步枢赔，找到需要刪除的pre節(jié)點。
while(i<n){
first=first->next;
i++;
}
//主要為了判斷是否是刪除首元素
if(!first){
return head -> next;
}
while(first->next!=NULL){
first=first->next;
second=second->next;
}
ListNode* tmp=second->next;
second->next=second->next->next;
delete tmp;
return head;
}
};
83.刪除排序鏈表中的重復(fù)元素
給定一個排序鏈表曙寡，刪除所有重復(fù)的元素糠爬，使得每個元素只出現(xiàn)一次。
示例 1:
輸入: 1->1->2
輸出: 1->2
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur=head;
while(cur!=NULL &&cur->next!=NULL){
if(cur->next->val==cur->val){
cur->next=cur->next->next;
}else{
cur=cur->next;
}
}
return head;
}
};
82.刪除排序鏈表中的重復(fù)元素II
給定一個排序鏈表举庶，刪除所有含有重復(fù)數(shù)字的節(jié)點执隧，只保留原始鏈表中 沒有重復(fù)出現(xiàn) 的數(shù)字。
提示：需要兩個指針户侥；一個用來遍歷镀琉，另一個用來刪除。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode dummyNode(-1);
ListNode* pre=&dummyNode;
ListNode* cur=head;
ListNode* tmp;
int n,val;
while(cur){
tmp = cur;
for(n=0,val=cur->val;cur!=NULL && cur->val==val;++n){
cur=cur->next;
}
if (n==1){
pre->next=tmp;
pre=pre->next;
}
}
pre->next=NULL;
return dummyNode.next;
}
};
1171.從鏈表中刪去總和值為0的連續(xù)節(jié)點
給你一個鏈表的頭節(jié)點 head蕊唐，請你編寫代碼屋摔，反復(fù)刪去鏈表中由 總和 值為 0 的連續(xù)節(jié)點組成的序列，直到不存在這樣的序列為止替梨。刪除完畢后钓试，請你返回最終結(jié)果鏈表的頭節(jié)點。
你可以返回任何滿足題目要求的答案副瀑。（注意弓熏，下面示例中的所有序列，都是對 ListNode 對象序列化的表示糠睡。）
提示：我們可以考慮如果給的入?yún)⒉皇擎湵硎菙?shù)組的話挽鞠，只需要求出前綴和，對于前綴和相同的項，那他們中間的部分即是可以消除掉的信认，比如以 [1, 2, 3, -3, 4] 為例材义，其前綴和數(shù)組為 [1, 3, 6, 3, 7] ，我們發(fā)現(xiàn)有兩項均為 3嫁赏，則 6 和 第二個 3 所對應(yīng)的原數(shù)組中的數(shù)字是可以消掉的其掂。換成鏈表其實也是一樣的思路，把第一個 3 的 next 指向第二個 3 的 next 即可橄教。
示例 1：
輸入：head = [1,2,-3,3,1]
輸出：[3,1]
提示：答案 [1,2,1] 也是正確的清寇。
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
// 求和喘漏，當(dāng)出現(xiàn)重復(fù)是 證明兩個重復(fù)節(jié)點之間的數(shù)據(jù)可以被刪除护蝶；
// 然后繼續(xù)遞歸； 返回值為dummy->next翩迈；
if (head==NULL){
return head;
}
ListNode dummy(0);
dummy.next=head;
ListNode* dummyPtr=&dummy;
map<int,ListNode*> map;
map[0]=dummyPtr;
int sum=0;
while(head!=NULL){
sum+=head->val;
if(map.find(sum)!=map.end()){
map[sum]->next=head->next;
return removeZeroSumSublists(dummy.next);
}else{
map[sum]=head;
head=head->next;
}
}
return dummy.next;
}
};
3.合并鏈表
合并鏈表持灰，需要注意頭節(jié)點dummyNode的使用。另外為了降低復(fù)雜度负饲，可以考慮使用歸并算法堤魁。
21.合并兩個有序鏈表
將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的返十。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy = ListNode(-1); // 創(chuàng)建椡兹空間對象即可。
ListNode* prev = &dummy; // 注意這里需要取地址&
while(l1 != NULL && l2 != NULL) {
if(l1->val <= l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
prev->next = l1 != NULL ? l1 : l2;
return dummy.next;
}
};
23.合并K個有序鏈表
題解：已經(jīng)實現(xiàn)了合并兩個有序鏈表了洞坑，那么其實可以使用歸并的思想進(jìn)行合并k個鏈表盲链，兩兩合并，時間復(fù)雜度為Nlogk
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len = lists.size();
if(len < 1) return NULL;
while(len>1){
int m = (len + 1) / 2;
for(int i=0;i<m && i+m < len;++i){
lists[i] = mergeTwoLists(lists[i],lists[i+m]);
}
len = m;
}
return lists[0];
}
2. 兩數(shù)相加
給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)迟杂。其中刽沾，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字排拷。
如果侧漓，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和监氢。
您可以假設(shè)除了數(shù)字 0 之外布蔗，這兩個數(shù)都不會以 0 開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
題解：新的節(jié)點等與兩個節(jié)點的(val+進(jìn)位)%10; 下一輪的進(jìn)位為(val+進(jìn)位)/10浪腐；
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *root=new ListNode(0);
ListNode *cur=root;
ListNode *tmp;
int c=0;
while(l1!=NULL || l2!=NULL || c!=0){ //注意邊界條件纵揍，可能最后只有進(jìn)位，需要創(chuàng)建新的節(jié)點
int v1=l1?l1->val:0;
int v2=l2?l2->val:0;
int sum=v1+v2+c;
c=sum/10;
tmp=new ListNode(sum%10);
cur->next=tmp;
cur=tmp;
if (l1){
l1=l1->next; // 注意邊界條件
}
if (l2){
l2=l2->next;
}
}
return root->next;
}
};
445.兩數(shù)相加II
給定兩個非空鏈表來代表兩個非負(fù)整數(shù)牛欢。數(shù)字最高位位于鏈表開始位置骡男。它們的每個節(jié)點只存儲單個數(shù)字。將這兩數(shù)相加會返回一個新的鏈表傍睹。你可以假設(shè)除了數(shù)字 0 之外隔盛，這兩個數(shù)字都不會以零開頭犹菱。
進(jìn)階:如果輸入鏈表不能修改該如何處理？換句話說吮炕，你不能對列表中的節(jié)點進(jìn)行翻轉(zhuǎn)腊脱。
示例:
輸入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出: 7 -> 8 -> 0 -> 7
題解：當(dāng)當(dāng)前值的計算依賴下一項的計算時，可以使用遞歸的方法來實現(xiàn)回溯龙亲。當(dāng)前值=（val+下一項的進(jìn)位）/10陕凹。需要兩個鏈表等長。 另一種辦法是借助額外的結(jié)構(gòu)鳄炉，來實現(xiàn)杜耙。例如棧/數(shù)組等。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
vector<ListNode*> l1v,l2v;
to_vector(l1,l1v);
to_vector(l2,l2v);
int i=l1v.size()-1, j=l2v.size()-1;
int d = 0;
ListNode *head = NULL;
while(i >= 0 || j >= 0){
if(i >= 0) d += l1v[i--]->val;
if(j >= 0) d += l2v[j--]->val;
ListNode* p = new ListNode(d%10);
p->next = head;
head = p;
d /= 10;
}
if(d) {
ListNode* p = new ListNode(d);
p->next = head;
head = p;
}
return head;
}
void to_vector(ListNode* a,vector<ListNode*>& v){
while(a){
v.push_back(a);
a = a->next;
}
}
};
4.重排鏈表
鏈表按照指定的規(guī)則進(jìn)行重新排序拂盯。比如首尾相連佑女，交換鏈表節(jié)點等等。
24.兩兩交換鏈表中的節(jié)點
給定一個鏈表谈竿，兩兩交換其中相鄰的節(jié)點团驱，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點內(nèi)部的值空凸，而是需要實際的進(jìn)行節(jié)點交換嚎花。
示例:
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
題解：聲明dummyNode，pre指向dummy呀洲。 start指向1紊选，end指向2. 讓pre.next=end;start.next=end.next;end.next=start. pre此刻再向前移動到start。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode temp = pre;
while(temp.next != null && temp.next.next != null) {
ListNode start = temp.next;
ListNode end = temp.next.next;
temp.next = end;
start.next = end.next;
end.next = start;
temp = start;
}
return pre.next;
}
}
25. k個一組反轉(zhuǎn)鏈表
給你一個鏈表两嘴，每 k 個節(jié)點一組進(jìn)行翻轉(zhuǎn)丛楚，請你返回翻轉(zhuǎn)后的鏈表憔辫。
k 是一個正整數(shù)趣些，它的值小于或等于鏈表的長度。
如果節(jié)點總數(shù)不是 k 的整數(shù)倍贰您，那么請將最后剩余的節(jié)點保持原有順序坏平。
示例 :
給定這個鏈表：1->2->3->4->5
當(dāng) k = 2 時，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k = 3 時锦亦，應(yīng)當(dāng)返回: 3->2->1->4->5
題解：合理利用cut函數(shù)舶替，每k個一組，切割成鏈表杠园，然后反轉(zhuǎn)顾瞪，然后注意進(jìn)行鏈接。每次反轉(zhuǎn)前判斷下長度是否達(dá)到k。當(dāng)對頭節(jié)點有進(jìn)行操作是陈醒，注意使用dummyNode惕橙。 主要要保持鏈表直接的連接。
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummyHead(0);
dummyHead.next=head;
auto cur=dummyHead.next;
auto tail = &dummyHead;
while(cur){
auto left = cur;
cur = cut(left, k); // left->@->@ right->@->@->@...
tail->next = reverseList(left,k);
while(tail->next){
tail=tail->next;
}
}
return dummyHead.next;
}
// k個一組進(jìn)行反轉(zhuǎn)钉跷，采用cut函數(shù)弥鹦，連接的時候，注意保證尾部正確爷辙。
ListNode* cut(ListNode* head,int k){
auto p=head;
while(--k && p){
p=p->next;
}
if(!p){
return nullptr;
}
auto next=p->next;
p->next=nullptr;
return next;
}
ListNode* reverseList(ListNode* head,int k) {
struct ListNode* p=head;
while(p!=NULL){
p=p->next;
k--;
}
if (k>0){
return head;
}
struct ListNode* pre=NULL;
struct ListNode* cur=head;
struct ListNode* tmp=NULL;
while(cur){
tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};
61.旋轉(zhuǎn)鏈表
給定一個鏈表彬坏，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點向右移動 k 個位置膝晾，其中 k 是非負(fù)數(shù)栓始。
輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL
題解：方法一：先連接，再旋轉(zhuǎn)玷犹。再斷開混滔。方法二：可以先整體逆序洒疚，然后前k個逆序歹颓，后n-k個逆序。
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head==NULL){
return NULL;
}
if (head->next==NULL){
return head;
}
ListNode *cur=head;
int n=1;
while(cur->next!=NULL){
cur=cur->next;
n++;
}
cur->next=head;
ListNode *new_tail = head;
int i=0;
for(i=0;i<n - k % n - 1;++i){
new_tail=new_tail->next;
}
ListNode* tmp=new_tail->next;
new_tail->next=NULL;
return tmp;
}
};
143.重排鏈表
給定一個單鏈表 L：L0→L1→…→Ln-1→Ln 油湖，
將其重新排列后變?yōu)椋?L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是單純的改變節(jié)點內(nèi)部的值巍扛，而是需要實際的進(jìn)行節(jié)點交換。
給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.
給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.
經(jīng)典問題：考察快慢指針找中間節(jié)點乏德；分隔鏈表撤奸；鏈表反轉(zhuǎn)，鏈表合并喊括。需要考慮將中間節(jié)點分配到第一個鏈表還是第二個鏈表胧瓜。考慮清楚邊界條件郑什。
class Solution {
public:
void reorderList(ListNode* head) {
// 先快慢指針找到中間節(jié)點府喳，然后對后面的反轉(zhuǎn)，最后合并
if(head==NULL || head->next==NULL){
return ;
}
ListNode* slow=head;
ListNode* fast=head->next;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
ListNode* l2=slow->next;
slow->next=NULL;
ListNode* l1=head;
// 反轉(zhuǎn)list2
ListNode* pre=NULL;
ListNode* cur=l2;
ListNode* next;
while(cur!=NULL){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
l2=pre;
// 合并l1 l2
while(l2!=NULL){
slow=l1->next;
fast=l2->next;
l1->next=l2;
l2->next=slow;
l1=slow;
l2=fast;
}
return;
}
};
147.鏈表進(jìn)行插入排序
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode h(-1);
h.next = head;
ListNode* pre = &h;
ListNode* cur = head;
ListNode* lat;
ListNode* tmp;
while (cur != NULL) {
lat = cur->next; // 記錄下一個要插入排序的值
if (lat != NULL && lat->val < cur->val) {
// 只有 cur.next 比 cur 小才需要向前尋找插入點
while (pre->next != NULL && pre->next->val < lat->val) {
pre = pre->next; // 繼續(xù)向后移動
}
// 找到要插入的位置蘑拯，此時 pre 節(jié)點后面的位置就是 lat 要插入的位置
tmp = pre->next;
pre->next = lat;
cur->next = lat->next;// 保證cur不斷
lat->next = tmp;
pre = &h;// 由于每次都是從前往后找插入位置钝满，所以需要每次插入完成后要讓 pre 復(fù)位
} else {
// 都這直接把 cur 指針指向到下一個
cur = lat;
}
}
return h.next;
}
};
148.排序鏈表
在 O(n log n) 時間復(fù)雜度和常數(shù)級空間復(fù)雜度下，對鏈表進(jìn)行排序申窘。
題解：要求時間復(fù)雜度弯蚜，考慮到歸并排序。兩兩合并剃法，需要logn次碎捺。每次進(jìn)行n個比較。需要注意的點；cut函數(shù)實現(xiàn)收厨，合并鏈個有序鏈表悍引；dummyNode使用；鏈表的連接帽氓；等等趣斤。
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode dummyHead(0);
dummyHead.next=head;
auto p=head;
int length=len(p);
for (int size=1;size<length;size<<=1){
auto cur=dummyHead.next;
auto tail = &dummyHead;
while(cur){
auto left = cur;
auto right = cut(left, size); // left->@->@ right->@->@->@...
cur = cut(right, size); // left->@->@ right->@->@ cur->@->..
tail->next = merge(left, right);
while(tail->next){
tail=tail->next;
}
}
}
return dummyHead.next;
}
int len(ListNode *p){
int length=0;
while (p) {
++length;
p = p->next;
}
return length;
}
ListNode* cut(ListNode* head,int n ){
auto p=head;
while(--n && p){
p=p->next;
}
if(!p){
return nullptr;
}
auto next=p->next;
p->next=nullptr;
return next;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummyHead(0);
auto p = &dummyHead;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
p = l1;
l1 = l1->next;
} else {
p->next = l2;
p = l2;
l2 = l2->next;
}
}
p->next = l1 ? l1 : l2;
return dummyHead.next;
}
};
5.分隔鏈表
86.分隔鏈表
給定一個鏈表和一個特定值 x，對鏈表進(jìn)行分隔黎休，使得所有小于 x 的節(jié)點都在大于或等于 x 的節(jié)點之前浓领。
你應(yīng)當(dāng)保留兩個分區(qū)中每個節(jié)點的初始相對位置。
題解：分解成兩個鏈表势腮，再連接联贩。注意dummyNode的使用。
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (head==NULL ||head->next==NULL){
return head;
}
ListNode l_head(-1);
ListNode r_head(-1);
ListNode* l=&l_head;
ListNode* r=&r_head;
auto l_tmp=l;
auto r_tmp=r;
while(head!=NULL){
if(head->val<x){
l->next=head;
l=l->next;
}else{
r->next=head;
r=r->next;
}
head=head->next;
}
l->next=r_tmp->next;
r->next=NULL;
return l_tmp->next;
}
};
109.有序鏈表轉(zhuǎn)換二叉搜索樹
給定一個單鏈表捎拯，其中的元素按升序排序泪幌，將其轉(zhuǎn)換為高度平衡的二叉搜索樹。
本題中署照，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1祸泪。
示例:
給定的有序鏈表： [-10, -3, 0, 5, 9],
一個可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個高度平衡二叉搜索樹：
0
/ \
-3 9
/ /
-10 5
題解：二叉搜索樹的前序遍歷為有序數(shù)組。那么對于鏈表中間節(jié)點即為跟節(jié)點建芙。采用遞歸進(jìn)行遍歷即可没隘。
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
//核心思想，中心節(jié)點就是根節(jié)點禁荸，遞歸構(gòu)造左右子節(jié)點右蒲。
if(head==NULL){
return NULL;
}
ListNode* mid=getMidNode(head);
TreeNode* node=new TreeNode(mid->val);
if (head==mid){
return node;
}
node->left=sortedListToBST(head);
node->right=sortedListToBST(mid->next);
return node;
}
// 查找中間節(jié)點并返回。并分割left鏈表最后指向NULL赶熟。
ListNode* getMidNode(ListNode *head){
ListNode* pre=NULL;
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL && fast->next!=NULL){
pre=slow;
slow=slow->next;
fast=fast->next->next;
}
if (pre!=NULL){
pre->next=NULL;
}
return slow;
}
};
725.分隔鏈表
給定一個頭結(jié)點為 root 的鏈表, 編寫一個函數(shù)以將鏈表分隔為 k 個連續(xù)的部分瑰妄。
每部分的長度應(yīng)該盡可能的相等: 任意兩部分的長度差距不能超過 1，也就是說可能有些部分為 null映砖。
這k個部分應(yīng)該按照在鏈表中出現(xiàn)的順序進(jìn)行輸出间坐，并且排在前面的部分的長度應(yīng)該大于或等于后面的長度。
返回一個符合上述規(guī)則的鏈表的列表啊央。
舉例： 1->2->3->4, k = 5 // 5 結(jié)果 [ [1], [2], [3], [4], null ]
示例 1：
輸入:
root = [1, 2, 3], k = 5
輸出: [[1],[2],[3],[],[]]
解釋:
輸入輸出各部分都應(yīng)該是鏈表眶诈，而不是數(shù)組。
例如, 輸入的結(jié)點 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null瓜饥。
第一個輸出 output[0] 是 output[0].val = 1, output[0].next = null逝撬。
最后一個元素 output[4] 為 null, 它代表了最后一個部分為空鏈表。
示例 2：
輸入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
輸出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解釋:
輸入被分成了幾個連續(xù)的部分乓土，并且每部分的長度相差不超過1.前面部分的長度大于等于后面部分的長度宪潮。
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* root, int k) {
// 遍歷root的長度溯警，得到len。
// if len<=k ; 那么每個都是獨立節(jié)點狡相，再增加k-len個空節(jié)點梯轻。
// if len>k; 那么切分為 len/k 個片段；其中 前 len%k個片段尽棕，長度為 len/k + 1;
// 實現(xiàn)cut(ListNode* head,int k); 切割前k個節(jié)點喳挑，返回第k+1個節(jié)點后的鏈表
// 循環(huán)切割，時間復(fù)雜度為O(N)
vector<ListNode*> vec;
ListNode* cur=root;
int len=getLen(root);
if (len<k){
for(int i=0;i<k;i++){
vec.push_back(cur);
cur=cut(cur,1);
}
}else{
int step=len/k;
int m=len%k;
int i=0;
for (i=0;i<m;i++){
vec.push_back(cur);
cur=cut(cur,step+1);
}
for(i=m;i<k;i++){
vec.push_back(cur);
cur=cut(cur,step);
}
}
return vec;
}
int getLen(ListNode* head){
if(head==NULL){
return 0;
}
int len=0;
ListNode* cur=head;
while(cur){
cur=cur->next;
len++;
}
return len;
}
ListNode* cut(ListNode* head,int k){
while(k>1 && head){
head=head->next;
k--;
}
if (head==NULL){
return NULL;
}
ListNode* tmp=head->next;
head->next=NULL;
return tmp;
}
};
6.使用額外結(jié)構(gòu)降低時間復(fù)雜度
138.復(fù)制帶隨機(jī)指針的鏈表
給定一個鏈表滔悉，每個節(jié)點包含一個額外增加的隨機(jī)指針伊诵，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。
要求返回這個鏈表的深拷貝回官。
題解：先全部復(fù)制一遍曹宴，再進(jìn)行指針關(guān)聯(lián)
class Node {
public:
int val;
Node* next;
Node* random;
Node() {}
Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
// hash 空間復(fù)雜O(N)
// 原地復(fù)制 空間復(fù)雜O(1) 復(fù)制節(jié)點 復(fù)制random 拆鏈表
Node* copyRandomList(Node* head) {
if(head==nullptr){
return nullptr;
}
map<Node*,Node*> map;
Node* cur=head;
while(cur){
map[cur]=new Node(cur->val,nullptr,nullptr);
cur=cur->next;
}
cur=head;
while(cur){
map[cur]->next=map[cur->next];
map[cur]->random=map[cur->random];
cur=cur->next;
}
return map[head];
}
};
817.鏈表組件
給定一個鏈表（鏈表結(jié)點包含一個整型值）的頭結(jié)點 head。
同時給定列表 G歉提，該列表是上述鏈表中整型值的一個子集笛坦。
返回列表 G 中組件的個數(shù)，這里對組件的定義為：鏈表中一段最長連續(xù)結(jié)點的值（該值必須在列表 G 中）構(gòu)成的集合苔巨。
示例 1：
輸入:
head: 0->1->2->3
G = [0, 1, 3]
輸出: 2
解釋:
鏈表中,0 和 1 是相連接的版扩，且 G 中不包含 2，所以 [0, 1] 是 G 的一個組件恋拷，同理 [3] 也是一個組件资厉，故返回 2。
示例 2：
輸入:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
輸出: 2
解釋:
鏈表中蔬顾，0 和 1 是相連接的，3 和 4 是相連接的湘捎，所以 [0, 1] 和 [3, 4] 是兩個組件诀豁，故返回 2。
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
set<int> m_set;
for (int i=0;i<G.size();i++){
m_set.insert(G[i]);
}
ListNode* cur=head;
int num = 0;
while(cur){
if(m_set.find(cur->val)!= m_set.end() && (cur->next==NULL || m_set.find(cur->next->val)== m_set.end())){
num++;
}
cur=cur->next;
}
return num;
}
};
1019.鏈表中下一個更大節(jié)點
給出一個以頭節(jié)點 head 作為第一個節(jié)點的鏈表窥妇。鏈表中的節(jié)點分別編號為：node_1, node_2, node_3, ... 舷胜。
每個節(jié)點都可能有下一個更大值（next larger value）：對于 node_i，如果其 next_larger(node_i) 是 node_j.val活翩，那么就有 j > i 且 node_j.val > node_i.val烹骨，而 j 是可能的選項中最小的那個。如果不存在這樣的 j材泄，那么下一個更大值為 0 沮焕。
返回整數(shù)答案數(shù)組 answer，其中 answer[i] = next_larger(node_{i+1}) 拉宗。
注意：在下面的示例中峦树，諸如 [2,1,5] 這樣的輸入（不是輸出）是鏈表的序列化表示辣辫，其頭節(jié)點的值為 2，第二個節(jié)點值為 1魁巩，第三個節(jié)點值為 5 急灭。
示例 1：
輸入：[2,1,5]
輸出：[5,5,0]
示例 2：
輸入：[2,7,4,3,5]
輸出：[7,0,5,5,0]
示例 3：
輸入：[1,7,5,1,9,2,5,1]
輸出：[7,9,9,9,0,5,0,0]
class Solution {
public:
//題解，使用棧先進(jìn)后出谷遂。找到第一個比較大的就更新對應(yīng)的數(shù)組值葬馋。
vector<int> nextLargerNodes(ListNode* head) {
int count = 0; //計數(shù)，作為下標(biāo)
vector<int> result;
stack<pair<int, int>> tmp; //first為val肾扰，second為下標(biāo)
while (head)
{
result.push_back(0); //給result數(shù)組后面+0点楼，1為保證長度，2是默認(rèn)值（后無更大的值的話）為0
while (!tmp.empty() &&
head->val > tmp.top().first) //棧不為空且head指針的val值大于棧頂?shù)脑氐闹? {
result[tmp.top().second] = head->val; //result數(shù)組修改白对，滿足題意要求的最大值掠廓，然后出棧，繼續(xù)循環(huán)
tmp.pop();
}
tmp.push(make_pair(head->val, count++)); //count++計數(shù)
head = head->next; //下一個節(jié)點
}
return result;
}
};
7.快慢指針
160.相交鏈表
編寫一個程序甩恼，找到兩個單鏈表相交的起始節(jié)點蟀瞧。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int aLen=0;
int bLen=0;
ListNode *curA=headA;
ListNode *curB=headB;
while(curA!=NULL){
curA=curA->next;
aLen++;
}
while(curB!=NULL){
curB=curB->next;
bLen++;
}
int i=0;
curA=headA;
curB=headB;
if (aLen>bLen){
for(i=0;i<aLen-bLen;i++){
curA=curA->next;
}
}else{
for(i=0;i<bLen-aLen;i++){
curB=curB->next;
}
}
while(curA){
if(curA==curB){
return curA;
}else{
curA=curA->next;
curB=curB->next;
i++;
}
}
return NULL;
}
};
234.回文鏈表
請判斷一個鏈表是否為回文鏈表。
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL||head->next==NULL){
return true;
}
ListNode* slow=head;
ListNode* fast=head->next;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
ListNode* r=resver(slow->next);
while(r!=NULL){
if(r->val!=head->val){
return false;
}
r=r->next;
head=head->next;
}
return true;
}
ListNode* resver(ListNode* head){
if(head==NULL||head->next==NULL){
return head;
}
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* next;
while(cur!=NULL){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
328.奇偶鏈表
給定一個單鏈表条摸，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起悦污。請注意，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性钉蒲，而不是節(jié)點的值的奇偶性切端。
請嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)顷啼，時間復(fù)雜度應(yīng)為 O(nodes)踏枣，nodes 為節(jié)點總數(shù)。
示例 1:
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
示例 2:
輸入: 2->1->3->5->6->4->7->NULL
輸出: 2->3->6->7->1->5->4->NULL
說明:
應(yīng)當(dāng)保持奇數(shù)節(jié)點和偶數(shù)節(jié)點的相對順序钙蒙。
鏈表的第一個節(jié)點視為奇數(shù)節(jié)點茵瀑，第二個節(jié)點視為偶數(shù)節(jié)點，以此類推躬厌。
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head==NULL||head->next==NULL){
return head;
}
ListNode* t1=head;
ListNode* t2=head->next;
ListNode* t2head=t2; //必須先保存马昨，才可以保證鏈接。因為后續(xù)head->next 變了扛施。
while(t2!=NULL && t2->next!=NULL){
t1->next=t2->next;
t1=t1->next;
t2->next=t1->next;
t2=t2->next;
}
t1->next=t2head;
return head;
}
};
