【Leetcode -86.分隔链表 -92.反转链表Ⅱ】

Leetcode -86.分隔链表

题目：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。

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

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

我们的思路是，遍历链表的每个元素，如果比x小则拿下来放到一个small的结构体指针中；否则，放到一个large的指针中；最后，判断small是否为空，如果为空，则说明链表中的元素全都是比x大或等于x；否则，链表中的元素有比x大或等于，也有比x小的，这时候将small的尾部接到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;//从头开始遍历，到空结束while (head){//head的val比x小，放到smallif (head->val < x){//当small为空，即没有值的时候，small和smalltail都更新为当前的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;}}//当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这个链表不为空，就将small尾部的next接到large，然后再返回smallif (small)smalltail->next = large;//这种情况则是链表中的值全都大于或等于x，直接返回large即可elsereturn large;return small;}

Leetcode -92.反转链表Ⅱ

题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 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指针走到链表中left位置和right位置，反转left位置到right位置即可；当left为1，即在头节点的位置时，最终只需要返回反转后的链表；当left不在头节点的位置，我们用一个指针cur记录leftcur的前一个位置，我们只需要将cur->next 接到反转后的链表，并返回头节点即可；

当left = 1，right = 3：

反转后整理的链表，返回prev即可，即返回反转后的链表；

当left不为1，left = 2，right = 3：

在函数中反转后的链表如下两个图，所以需要将原链表中cur->next接到反转后的链表中，再返回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){//当左下标和右下标相同，不需要反转，返回headif (left == right)return head;struct ListNode* cur = head;struct ListNode* leftcur = head, * rightcur = head;//leftcur走到链表中left的位置while (--left){leftcur = leftcur->next;}//rightcur走到链表中right的位置while (--right){rightcur = rightcur->next;}//cur从头遍历，当cur等于leftcur或者cur->next等于leftcur时停下while (cur != leftcur && cur->next != leftcur){cur = cur->next;}//cur->next等于leftcur，反转leftcur到rightcur长度的链表//并且将cur的next接到反转后的链表去//返回头节点if (cur != leftcur){cur->next = Reverse(leftcur, rightcur);return head;}//cur等于leftcur，即cur = leftcur = head，//就反转leftcur到rightcur长度的链表，返回反转后的链表即可else{return Reverse(leftcur, rightcur);}}