92. 反转链表 II（数据结构系列）

92. 反转链表 II

• 题目
• 解题思路
• 代码

题目

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

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

解题思路

见书286

代码

/**
 * 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 {
    ListNode successor = null;//后驱节点

    /*
    反转链表中的前n个节点
    */
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {//经过下面的递归，一定会来到这里，把后驱节点赋上值。
            successor = head.next;//记录反转后的头节点 后面原来连接的那个节点
            return head;//反转一个节点，就是它自己
        }
        //以head.next为起点，需要反转前n-1个节点
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        head.next = successor;
        return last;
    }


    public ListNode reverseBetween(ListNode head, int m, int n) {

        if (head == null || head.next == null) {
            return head;
        }

        //base case  经过递归最终会来到这里的。
        if (m == 1) {//left=1,相当于链表开头的right个元素
            return reverseN(head, n);
        }

        /*对于head.next来说就是反转区间[left-1,right-1]
        reverseBetween();会返回反转后的链表头节点，head.next就是把反转后的头节点和head连接起来

         前进到反转的起点触发 base case
         */
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }
}