问题描述

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

反转链表中m ~ n的结点，注意1 <= m <= n <= length of list

举个例子：

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

解法1

Thanks Leetcode 92. Reverse Linked List II{:target=”_blank”}

先来看下示意图：

我们现在想把1 ~ 4进行反转。

来看第一步：

解释一下：

首先，明确一下，我们在第一步需要做什么事情？

反转1和2两个结点。

那么，我们先把目光放在cur结点上，也就是1。

根据我们目标，cur的下一个结点指向什么？

结点3，也就是cur.next.next，来看下如何表示：

cur.next = cur.next.next

注意，我们需要提前保存cur.next的内容，防止被覆盖。

所以：

ListNode next = cur.next
cur.next = next.next

继续，那么结点2的下一个结点应该指向谁？

结点1，也就是pre.next，来看下如何表示：

next.next = pre.next

最后，pre的下一个结点应该指向谁？

结点2，也就是next，所以：

pre.next = next

来看下完整的四步操作：

ListNode next = cur.next;
cur.next  = next.next;
next.next = pre.next;
pre.next  = next;

再来看第二步：

注意，此时2 -> 1已经反转了，所以cur = 1, next = 3，pre还是那个pre。

再注意一点，cur永远都是1！！！

最后一步：

看下反转后的结果：

来看下完整实现：

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

        int k = n - m;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;

        while (m-- > 1){
            pre = pre.next;
        }

        ListNode cur = pre.next;
        while (k-- > 0){
            ListNode next = cur.next;
            cur.next  = next.next;
            next.next = pre.next;
            pre.next  = next;
        }

        return dummy.next;
    }
}

Enjoy it !

再来看下我一开始的想到的解决方案：

首先，找到需要反转的区域，提前保存前一个结点pre。

然后，反转该区域，该操作分为三步，先截断、再反转、最后连接。

连接时需要注意：先要遍历到最后一个结点。

最后，将pre拼上反转后的链表。

相等麻烦，来看下代码：

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

        int gap = n - m;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;

        while (m-- > 1){
            cur = cur.next;
        }

        ListNode retNode = reverse(cur.next, gap);
        cur.next = retNode;
        return dummy.next;
    }

    private ListNode reverse(ListNode head, int gap){

        if (head == null) return null;
        ListNode cur = head;
        while (gap-- > 0){
            cur = cur.next;
        }
        ListNode conn = cur.next;

        cur.next = null;
        cur = head;
        ListNode ret = doReverse(cur);
        ListNode last = ret;
        // Be careful.
        while (last != null && last.next != null){
            last = last.next;
        }
        last.next = conn;
        return ret;
    }

    private ListNode doReverse(ListNode head){

        ListNode ret = null;
        while (head != null){
            ListNode next = head.next;
            head.next = ret;
            ret = head;
            head = next;
        }
        return ret;
    }
}