题目地址

https://leetcode-cn.com/problems/reverse-linked-list-ii/

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

反转整个链表

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;

        // 反转 head.next 链表
        ListNode reversedHead = reverse(head.next);
        
        // 反转后 head.next 是尾节点
        // 把 head 追加到 尾节点即可
        head.next.next = head;
        head.next = null;
        return reversedHead;
    }

参考 leetcode 题目： 206. 反转链表

题解

找到 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) {
        ListNode prevLeftNode = head, rightNode = head;
        int count = 0;

        ListNode savedHead = head;
        while (head != null) {
            count++;
            if (left-1 == count) {
                prevLeftNode = head;
            }
            if (right == count) {
                rightNode = head;
            }
            head = head.next;
        }

        if (left == 1) {
            return reverse(savedHead, rightNode);
        }

        ListNode reversedList = reverse(prevLeftNode.next, rightNode);
        prevLeftNode.next = reversedList;
        return savedHead;
    }

    public ListNode reverse(ListNode head, ListNode tail) {
        if (head == null || head.next == null || head == tail) return head;

        // 反转 head.next 链表
        ListNode reversedHead = reverse(head.next, tail);
        
        // 反转后 head.next 是尾节点
        // 把 head 追加到 尾节点即可
        ListNode oldNext = head.next.next;
        head.next.next = head;
        head.next = oldNext;
        return reversedHead;
    }
}

另一种解法

反转链表前 N 个元素

    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            return head;
        }

        // 反转 head.next 链表
        ListNode reversedHead = reverseN(head.next, n - 1);
        
        // 反转后 head.next 是尾节点
        // 把 head 追加到 尾节点即可
        ListNode successor = head.next.next;
        head.next.next = head;
        head.next = successor;
        return reversedHead;
    }

完整的代码如下所示：

/**
 * 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) {
        // left == 1 时，就是反转链表前 right 个元素
        if (left == 1) {
            return reverseN(head, right);
        }

        // 因为 [1 ~ left) 区间的链表不需要反转
        // 因此把反转后的链表 head.next，再追加到 head 后面即可
        // 反转 head.next 链表时，因为链表后移了一步，因此 left 和 right 都要减 1
        head.next = reverseBetween(head.next, left-1, right-1);
        return head;
    }

    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            return head;
        }

        // 反转 head.next 链表
        ListNode reversedHead = reverseN(head.next, n - 1);
        
        // 反转后 head.next 是尾节点
        // 把 head 追加到 尾节点即可
        ListNode successor = head.next.next;
        head.next.next = head;
        head.next = successor;
        return reversedHead;
    }
}