2021-02-07 92. 反转链表 II

题目地址

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

思路

1. 链表反转过程中，链表会被分成3段。

   
   image.png
2. 将m-n反转再拼上去就行。
   要注意有没有第一段， 如果从头开始的就不用拼第一段和第二段，否则就会自己指向自己出现死循环。
   而第二段和第三段的拼接其实可以在第二段反转的时候顺手完成，因为第二段反转完成的时候，刚开始的头是尾，cur是下一个要反转的元素，反转完成时它就指向第三段的头。

题解

/**
 * 执行用时: 0 ms
 * 内存消耗: 36.1 MB
 * 提交时间：1 小时前
 * @Author: vividzcs
 * @Date: 2021/2/6 11:15 下午
 */
public class ReverseBetween {
    public static void main(String[] args) {
        int[] arr = {3,5};
        ListNode head = ListNode.createListNode(arr);
        ListNode newHead = reverseBetween(head, 1, 2);
        ListNode.print(newHead);
    }

    private static ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) {
            return head;
        }
        ListNode temp = head;
        int index = 0;
        ListNode firstTail = temp;
        while (temp != null) {
            if (m == (index + 1)) {
                break;
            }
            index++;
            firstTail = temp;
            temp = temp.next;
        }
        ListNode newHead = reverse(temp, m, n);

        // 如果是从头开始的，就没有第一段，也就不用接
        if (index == 0) {
            return newHead;
        }

        // 有第一段，将第一段的尾接到第二段的头
        firstTail.next = newHead;
        return head;
    }

    private static ListNode reverse(ListNode head, int start, int end) {
        ListNode cur = head.next;
        ListNode pre = head;

        int index = start;
        while (cur != null) {
            if (end == index) {
                break;
            }
            index++;
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        // 将第二段和第三段接上
        head.next = cur;
        return pre;
    }
}