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小，放到small
		        if (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，然后再返回small
		    if (small)
		        smalltail->next = large;
		
		    //这种情况则是链表中的值全都大于或等于x，直接返回large即可
		    else
		        return 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)
		{
		    //当左下标和右下标相同，不需要反转，返回head
		    if (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);
		    }
		
		}