0092. Reverse Linked List II

---

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4

Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1

Output: [5]

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

---

解法1

从head开始计数, 从left的下一个开始,调换顺序, 直到大于right.

/**
 * 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;
        
        // 为了left=1时的计算方便, 在head之前增加一个dummy节点
        ListNode node = new ListNode(0, head);
        helper(null, node, head, left, right, 1);
        return node.next;
    }
    
    
    private void helper(ListNode nodeBeforeLeft, ListNode pre, ListNode cur, int left, int right, int index){
        // 当还没到left时, 单纯的递增index
        if(index < left)
            helper(null, cur, cur.next, left, right, index + 1);
        
        // 当到达left时, 记录下left的前一个节点
        else if(index == left)
            helper(pre, cur, cur.next, left, right, index + 1);
        
        // 当大于right时, 推出计算
        else if(index > right)
            return;
        
        // 当在left和right之间时, 总是把当前节点放到最开始left的位置
        else{
            ListNode next = cur.next;
            cur.next = nodeBeforeLeft.next;
            nodeBeforeLeft.next = cur;
            pre.next = next;
            helper(nodeBeforeLeft, pre, next, left, right, index + 1);
        }
            
            
    }
}