LeetCode 92. Reverse Linked List II

1. 題目描述

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.

2. 解題思路

和連結清單逆置的思路非常類似， 本質就是指針之間的互相倒騰。

3. code

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == nullptr)
            return nullptr;

        ListNode myhead(), *pre = &myhead, * cur = nullptr, * next = nullptr;
        myhead.next = head, cur = pre->next;
        int count = ;
        // locate pre
        while (count < m - ){
            cur = cur->next;
            pre = pre->next;
            count++;
        }
        ListNode * mycur = cur;

        // reverse
        ListNode * myend = nullptr;
        while (count < n){
            next = cur->next;
            cur->next = myend;
            myend = cur;
            cur = next;
            count++;
        }

        // connect
        pre->next = myend;
        mycur->next = next;

        return myhead.next;
    }
};
           

4. 大神代碼

非常類似的思路

/*
The basic idea is as follows:

(1) Create a new_head that points to head and use it to locate the immediate node before the m-th (notice that it is 1-indexed) node pre;

(2) Set cur to be the immediate node after pre and at each time move the immediate node after cur (named move) to be the immediate node after pre. Repeat it for n - m times.
*/
class Solution {  
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* new_head = new ListNode();
        new_head -> next = head;
        ListNode* pre = new_head;
        for (int i = ; i < m - ; i++)
            pre = pre -> next;
        ListNode* cur = pre -> next;
        for (int i = ; i < n - m; i++) {
            ListNode* move = cur -> next; 
            cur -> next = move -> next;
            move -> next = pre -> next;
            pre -> next = move;
        }
        return new_head -> next;
    }
};