92. Reverse Linked List II

Description

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

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Solution

Iterative

思路如下：

• 首先找到开始reverse的节点的前一个节点before
• reverse从before + 1到before + n - m + 1这个区间的节点
• 把链表拼起来

是一道考察细节的题，很容易把指针搞乱掉啊，必须二刷。

/**
 * 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 (m < 1 || n < 1 || m >= n) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode before = dummy;
        
        for (int i = 0; i < m - 1; ++i) {
            before = before.next;
        }
        
        // revert [indexOf(before) + 1, indexOf(before) + n - m + 1]
        ListNode prev = before;
        ListNode curr = prev.next;
        for (int i = 0; i < n - m + 1; ++i) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        before.next.next = curr;
        before.next = prev;
        
        return dummy.next;
    }
}

Insert node, time O(n), space O(1)

二刷发现没多难啊，换一种思路，将m到n之间的每个节点移到m-1后面即可。

/**
 * 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 (m == n) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode tail = dummy;
        
        for (int i = 1; i < m; ++i) {
            tail = tail.next;
        }
        
        ListNode prev = tail.next;
        for (int i = 0; i < n - m; ++i) {
            // move prev.next to the between of tail and tail.next
            ListNode curr = prev.next;
            prev.next = curr.next;
            curr.next = tail.next;
            tail.next = curr;
        }
        
        return dummy.next;
    }
}