Reverse Linked List II

https://leetcode.com/problems/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.

Thoughts

1. 基本思路不难想，从第m个开始翻转，要走到m - 1个，也就是跳m-2次next，然后从m开始翻转后面n - m + 1个nodes.

2. Corner cases很多，要加上m == 1 时相当于翻转整个链表。m== n时直接返回head.

Code

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n) return head;
        auto cur = head;
        if (m == 1) {
            return reverse(head, n);
        }
        for (int i = 0; i < m - 2; ++i) {
            cur = cur->next;
        }
        cur->next = reverse(cur->next, n - m + 1);
        return head;
    }

private:
    ListNode* reverse(ListNode *head, int count) {
        ListNode *cur = head, *prior = nullptr;
        for (int i = 0; i < count; ++i) {
            const auto next = cur->next;
            cur->next = prior;
            prior = cur;
            cur = next;
        }
        head->next = cur;
        return prior;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head, int length) {
        ListNode node = head;
        if (node == null || node.next == null) {
            return node;
        }
        ListNode prior = null;
        for (int i = 0; i < length; i++) {
            ListNode next = node.next;
            node.next = prior;
            prior = node;
            node = next;
        }

        head.next = node;
        return prior;
 // 注意这里
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) {
            return head;
        }
        ListNode node = head;
        if (m == 1) {
            return reverseList(head, n);
        }
        // how many jumps are there if from 1, ending at m - 1 (1)
        for (int i = 1; i < m - 1; i++) {
            node = node.next;
        }
        // reverse from m (2) to n (4), n - m + 1 edges/nodes to be reversed
        node.next = reverseList(node.next, n - m + 1);

        return head;

    }
}

Analysis

Errors:

1. 翻转没用prior而是用的next算法，逻辑出现了混乱。

做题耗时: 1 hour

时间复杂度O(n), 空间O(1).