Leetcode -86.分隔鏈表

題目：給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)特定值 x ，請(qǐng)你對(duì)鏈表進(jìn)行分隔，使得所有 小于 x 的節(jié)點(diǎn)都出現(xiàn)在 大于或等于 x 的節(jié)點(diǎn)之前。
你應(yīng)當(dāng) 保留 兩個(gè)分區(qū)中每個(gè)節(jié)點(diǎn)的初始相對(duì)位置。

示例 1：
輸入：head = [1, 4, 3, 2, 5, 2], x = 3
輸出：[1, 2, 2, 4, 3, 5]

示例 2：
輸入：head = [2, 1], x = 2
輸出：[1, 2]

我們的思路是，遍歷鏈表的每個(gè)元素，如果比x小則拿下來放到一個(gè)small的結(jié)構(gòu)體指針中；否則，放到一個(gè)large的指針中；最后，判斷small是否為空，如果為空，則說明鏈表中的元素全都是比x大或等于x；否則，鏈表中的元素有比x大或等于，也有比x小的，這時(shí)候?qū)mall的尾部接到large上即可；

		struct ListNode* partition(struct ListNode* head, int x){//small放比x小的值//large放大于等于x的值//smalltail和largetail分別是它們的尾struct ListNode* large = NULL, * small = NULL;struct ListNode* largetail = NULL, * smalltail = NULL;//從頭開始遍歷，到空結(jié)束while (head){//head的val比x小，放到smallif (head->val < x){//當(dāng)small為空，即沒有值的時(shí)候，small和smalltail都更新為當(dāng)前的head//head迭代往后走，尾的next置空if (small == NULL){small = smalltail = head;head = head->next;smalltail->next = NULL;}//否則，更新尾并迭代head即可else{smalltail->next = head;head = head->next;smalltail = smalltail->next;smalltail->next = NULL;}}//當(dāng)head的val比x大或等于x，與上面類似else{if (large == NULL){large = largetail = head;head = head->next;largetail->next = NULL;}else{largetail->next = head;head = head->next;largetail = largetail->next;largetail->next = NULL;}}}//如果鏈表中的值有大有小，即small這個(gè)鏈表不為空，就將small尾部的next接到large，然后再返回smallif (small)smalltail->next = large;//這種情況則是鏈表中的值全都大于或等于x，直接返回large即可elsereturn large;return small;}

Leetcode -92.反轉(zhuǎn)鏈表Ⅱ

題目：給你單鏈表的頭指針 head 和兩個(gè)整數(shù) left 和 right ，其中 left <= right 。
請(qǐng)你反轉(zhuǎn)從位置 left 到位置 right 的鏈表節(jié)點(diǎn)，返回 反轉(zhuǎn)后的鏈表 。

示例 1：
輸入：head = [1, 2, 3, 4, 5], left = 2, right = 4
輸出：[1, 4, 3, 2, 5]

示例 2：
輸入：head = [5], left = 1, right = 1
輸出：[5]

我們的思路是，使用leftcur和rightcur指針走到鏈表中l(wèi)eft位置和right位置，反轉(zhuǎn)left位置到right位置即可；當(dāng)left為1，即在頭節(jié)點(diǎn)的位置時(shí)，最終只需要返回反轉(zhuǎn)后的鏈表；當(dāng)left不在頭節(jié)點(diǎn)的位置，我們用一個(gè)指針cur記錄leftcur的前一個(gè)位置，我們只需要將cur->next 接到反轉(zhuǎn)后的鏈表，并返回頭節(jié)點(diǎn)即可；

當(dāng)left = 1，right = 3：

反轉(zhuǎn)后整理的鏈表，返回prev即可，即返回反轉(zhuǎn)后的鏈表；

當(dāng)left不為1，left = 2，right = 3：

在函數(shù)中反轉(zhuǎn)后的鏈表如下兩個(gè)圖，所以需要將原鏈表中cur->next接到反轉(zhuǎn)后的鏈表中，再返回head；

代碼以及注釋：

		struct ListNode* Reverse(struct ListNode* prev, struct ListNode* dest){struct ListNode* curr = prev->next;prev->next = dest->next;while (prev != dest){struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}struct ListNode* reverseBetween(struct ListNode* head, int left, int right){//當(dāng)左下標(biāo)和右下標(biāo)相同，不需要反轉(zhuǎn)，返回headif (left == right)return head;struct ListNode* cur = head;struct ListNode* leftcur = head, * rightcur = head;//leftcur走到鏈表中l(wèi)eft的位置while (--left){leftcur = leftcur->next;}//rightcur走到鏈表中right的位置while (--right){rightcur = rightcur->next;}//cur從頭遍歷，當(dāng)cur等于leftcur或者cur->next等于leftcur時(shí)停下while (cur != leftcur && cur->next != leftcur){cur = cur->next;}//cur->next等于leftcur，反轉(zhuǎn)leftcur到rightcur長(zhǎng)度的鏈表//并且將cur的next接到反轉(zhuǎn)后的鏈表去//返回頭節(jié)點(diǎn)if (cur != leftcur){cur->next = Reverse(leftcur, rightcur);return head;}//cur等于leftcur，即cur = leftcur = head，//就反轉(zhuǎn)leftcur到rightcur長(zhǎng)度的鏈表，返回反轉(zhuǎn)后的鏈表即可else{return Reverse(leftcur, rightcur);}}