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

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

Example:

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

AC代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (!head || !(head->next) || m == n) return head;
        ListNode *pre = NULL, *cur = head, *realPre = NULL, *realPost = NULL;
        int idx = 0;
        while (true) {
            idx++;
            if (idx < m) {
                pre = cur;
                cur = cur->next;
                continue;
            }
            if (idx == m) {
                if (m != 1) realPre = pre;
                realPost = cur;
            }
            if (idx <= n) {
                ListNode* tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }
            else {
                if (m != 1) realPre->next = pre;
                realPost->next = cur;
                break;
            }
        }
        if (m > 1)
            return head;
        else
            return pre;
    }
};

优化写法

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        for (int i = 0; i < m - 1; ++i) pre = pre->next;
        ListNode* cur = pre->next;
        for (int i = m; i < n; ++i) {
            ListNode* t=cur->next;
            cur->next=t->next;
            t->next=pre->next;
            pre->next=t;
        }
        return dummy->next;
    }
};

总结

看了别人的才意识到自己写的有多🍔，优化参考：https://www.cnblogs.com/grandyang/p/4306611.html