LeetCode 92. 反转链表 II-蒲公英云

LeetCode 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

为链表创建新的头结点，以便所有可能情况进行统一处理；
循环找到左节点leftNode及左节点前面的一个结点leftpre；
继续循环，找到右结点rightNode及右结点的next结点p；
利用链表翻转函数（递归翻转）将leftNode~rightNode区间的链表翻转；
leftpre.next连接rightNode;
leftNode.next连接p;

返回newhead头结点的next即可。

/**

Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
*/
class Solution {

public ListNode reverseBetween(ListNode head, int left, int right) {

    if(left==right) return head;
    int cnt=1;
    ListNode leftNode=null;
    ListNode newhead=new ListNode(0);
    newhead.next=head;
    ListNode leftpre=newhead;
    ListNode rightNode=null;
    ListNode p=head;
    while(cnt<left) {
        leftpre=leftpre.next;
        p=p.next;
        cnt++;
    }
    leftNode=p;
    while(cnt<right) {
        p=p.next;
        cnt++;
    }
    rightNode=p;
    p=p.next;
    rightNode.next=null;
    dfs(leftNode);
    leftpre.next=rightNode;
    leftNode.next=p;
    return newhead.next;
}
public ListNode dfs(ListNode head) {
    if(head==null) return new ListNode(0);
    ListNode tmp=dfs(head.next);
    tmp.next=head;
    head.next=null;
    return head;
}