[数据结构与算法]【LeetCode】Medium | 92. 反转链表 II （三指针）

题目：

给你单链表的头指针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]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出

思路：

一般情况分析：
① 找到left的前一个元素，right当前元素
② 将中间待反转的部分与前后断开
③ 反转中间部分
④ 链接前后

特殊情况分析：

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    struct ListNode*pleft=head;
    struct ListNode*pright=head;
    if(left==right)
       return head;
    while(left>2)
    {
        --left;
        pleft=pleft->next;
    }
    while(right!=1)
    {
        --right;
        pright=pright->next;
    }
    //保存left和right前后数据
    struct ListNode*n1=NULL;
    struct ListNode*n2=pleft;
    if(left!=1)
    {
        n2=pleft->next;
        pleft->next=NULL;
    }
    struct ListNode*n3=n2->next;
    struct ListNode*tempright=pright->next;
    pright->next=NULL;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    if(left==1)
    {
        head->next=tempright;
        return n1;
    }
    else
    {
        pleft->next=n1;
        while(n1->next)
        {
            n1=n1->next;
        }
        n1->next=tempright;
         return head;
    }

}