20200805-92-反转链表 II.md

每天一道leetCode

信息卡片

• 时间：2020-08-05
• 题目链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
• tag：链表 递归

### 题目描述

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

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

示例:

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

参考答案

非递归

使用双指针，先定位到需m，然后把m和n直接的节点逐一反转指向，同时注意要记录起始节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        ListNode cur = head, pre = null;
        while(m > 1) {
            pre = cur;
            cur = cur.next;
            m--;
            n--;
        }
        
        ListNode leftJoint = pre, rightJoint = cur;
        ListNode temp = null;
        while(n > 0) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            n--;
        }

        rightJoint.next = cur;
        if (leftJoint == null) {
            head = pre;
        } else {
            leftJoint.next = pre;
        }
        return head;
    }
}

递归

递归真是太巧妙了，具体看这里

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode successor;
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return reverseN(head, n);
        }
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}
``