?作者：小盧

專欄：《Leetcode》

喜歡的話：世間因?yàn)樯倌甑耐ι矶?#xff0c;而更加瑰麗。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ——《人民日報(bào)》

---

BM1?反轉(zhuǎn)鏈表?

描述：

給定一個(gè)單鏈表的頭結(jié)點(diǎn)pHead(該頭節(jié)點(diǎn)是有值的，比如在下圖，它的val是1)，長度為n，反轉(zhuǎn)該鏈表后，返回新鏈表的表頭。

數(shù)據(jù)范圍：0≤n≤1000

要求：空間復(fù)雜度 O(1)?，時(shí)間復(fù)雜度O(n)?。

如當(dāng)輸入鏈表{1,2,3}時(shí)，

經(jīng)反轉(zhuǎn)后，原鏈表變?yōu)閧3,2,1}，所以對應(yīng)的輸出為{3,2,1}。

以上轉(zhuǎn)換過程如下圖所示：

示例：

思路：

初始化：3個(gè)指針
1）pre指針指向已經(jīng)反轉(zhuǎn)好的鏈表的最后一個(gè)節(jié)點(diǎn)，最開始沒有反轉(zhuǎn)，所以指向nullptr
2）cur指針指向待反轉(zhuǎn)鏈表的第一個(gè)節(jié)點(diǎn)，最開始第一個(gè)節(jié)點(diǎn)待反轉(zhuǎn)，所以指向head
3）nex指針指向待反轉(zhuǎn)鏈表的第二個(gè)節(jié)點(diǎn)，目的是保存鏈表，因?yàn)閏ur改變指向后，后面的鏈表則失效了，所以需要保存
接下來，循環(huán)執(zhí)行以下三個(gè)操作
1）nex = cur->next, 保存作用
2）cur->next = pre 未反轉(zhuǎn)鏈表的第一個(gè)節(jié)點(diǎn)的下個(gè)指針指向已反轉(zhuǎn)鏈表的最后一個(gè)節(jié)點(diǎn)
3）pre = cur， cur = nex; 指針后移，操作下一個(gè)未反轉(zhuǎn)鏈表的第一個(gè)節(jié)點(diǎn)
循環(huán)條件，當(dāng)然是cur != nullptr
循環(huán)結(jié)束后，cur當(dāng)然為nullptr，所以返回pre，即為反轉(zhuǎn)后的頭結(jié)點(diǎn)?

代碼：

struct ListNode* ReverseList(struct ListNode* pHead ) {// write code herestruct ListNode*prep=NULL;struct ListNode*cur1=pHead;struct ListNode*cur2;while(cur1){cur2=cur1->next;cur1->next=prep;prep=cur1;cur1=cur2;}return prep;
}

NC21?鏈表內(nèi)指定區(qū)間反轉(zhuǎn)

鏈表內(nèi)指定區(qū)間反轉(zhuǎn)_?？皖}霸_?？途W(wǎng)

題目描述：

描述

將一個(gè)節(jié)點(diǎn)數(shù)為 size 鏈表 m?位置到?n 位置之間的區(qū)間反轉(zhuǎn)，要求時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)。
例如：
給出的鏈表為 1→2→3→4→5→NULL, m=2,n=4,
返回1→4→3→2→5→NULL.
?

數(shù)據(jù)范圍： 0<size≤1000，0<m≤n≤size，鏈表中每個(gè)節(jié)點(diǎn)的值滿足∣val∣≤1000

要求：時(shí)間復(fù)雜度 O(n)?，空間復(fù)雜度O(n)

進(jìn)階：時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)

示例1：

思路：

先找到m的位置然后從進(jìn)行翻轉(zhuǎn)就可以，看我注釋

• step 1：我們可以在鏈表前加一個(gè)表頭，后續(xù)返回時(shí)去掉就好了，因?yàn)槿绻獜逆湵眍^的位置開始反轉(zhuǎn)，在多了一個(gè)表頭的情況下就能保證第一個(gè)節(jié)點(diǎn)永遠(yuǎn)不會(huì)反轉(zhuǎn)，不會(huì)到后面去。
• step 2：使用兩個(gè)指針，一個(gè)指向當(dāng)前節(jié)點(diǎn)，一個(gè)指向前序節(jié)點(diǎn)。
• step 3：依次遍歷鏈表，到第m個(gè)的位置。
• step 4：對于從m到n這些個(gè)位置的節(jié)點(diǎn)，依次斷掉指向后續(xù)的指針，反轉(zhuǎn)指針方向。
• step 5：返回時(shí)去掉我們添加的表頭。

代碼：

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {// write code herestruct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));newhead->next=head;struct ListNode*cur1=head;struct ListNode*prep=newhead;for(int i=1;i<m;i++){//找到m的位置cur1=cur1->next;prep=prep->next;}for(int i=m;i<n;i++){struct ListNode* cur2=cur1->next;cur1->next=cur2->next;//防止找不到cur2后面的那個(gè)節(jié)點(diǎn)cur2->next=prep->next;//cur2一定在翻轉(zhuǎn)部分的最前面。//翻轉(zhuǎn)后在前面的節(jié)點(diǎn)一定在prep的后一個(gè)節(jié)點(diǎn)prep->next=cur2;}return newhead->next;
}