LeetCode 92. Reverse Linked List II

Problem

LeetCode 92. Reverse Linked List II

1. 题目简述

给出一个链表，和两个正整数m、n（1 <= m <= n <= length），翻转该链表的第m和n之间的元素。例如：

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

2. 算法思路

经典题目的难度加大的版本，难度在于我们需要找到起始位置和终止位置，基本思路如下：

1. 首先找到第m个元素ptr，以及它前面的那个元素pre，pre有可能为null；
2. 定义tail = ptr，因为翻转后，第m个元素就是翻转部分链表的结尾；
3. 定义con = pre，这个con是用来记录当前pre是否为null的，如果不为null值，就将con和反转后的表头相连，，为null就直接返回反转后的表头；
4. 定义tail = ptr，因为当前未翻转部分的表头ptr其实是反转后的末尾，记录一下，因为后面while循环后ptr就不在翻转列表里了，需要重新连一下。
5. while循环，记录post元素，将ptr的next指向pre，然后更改ptr和pre（这里有一个注意事项，就是翻转第一个元素的时候可能有人会觉得不合理，其实这只是暂存，while循环后面会修正的）。
6. 修正tail的指向；
7. 判断连接处con是否为空，如果不为空则连接，为空则不连接。

for循环

/**
 * 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 m, int n) {
        if (m == n) {
            return head;
        }

        ListNode ptr = head, pre = null;
        while (m > 1) {
            pre = ptr;
            ptr = ptr.next;
            m--;
            n--;
        }

        ListNode con = pre, tail = ptr;
        while (n > 0) {
            ListNode post = ptr.next;
            // 注意，对于第一个翻转的元素，这里只是暂存！！！后面ptr会变，这里其实是tail
            ptr.next = pre;
            pre = ptr;
            ptr = post;
            n--;
        }

        tail.next = ptr;
        // while循环结束时，ptr处于第n+1个元素，pre是原本的第n个元素
        if (con != null) {
            con.next = pre;
        } else {
            return pre;
        }

        return head;
    }
}