題目概要

將指定范圍內(nèi)的鏈表翻轉(zhuǎn)。

題目鏈接

Reverse Linked List II

題目解析

注意，題目中標(biāo)注了條件：$1\le m \le n \le length_of_list$
我們現(xiàn)在來關(guān)注翻轉(zhuǎn)某局部鏈表時(shí)，所需要進(jìn)行的操作：

 [+]->[+]->[o]->[o]->[o]->[o]->[o]->[x]->[+]->[+]->^
       ^                        ^    ^
       |                        |    |
      tail                 revTail revHead

上圖中[+]表示的結(jié)點(diǎn)為正常結(jié)點(diǎn)，而[o]為已經(jīng)被翻轉(zhuǎn)過的鏈表結(jié)點(diǎn)，[x]為正在被翻轉(zhuǎn)的結(jié)點(diǎn)。
易知此時(shí)需要進(jìn)行的操作如下：

revHead = revTail->next;
revTail->next = revHead->next;
revHead->next = tail->next;
tail->next = revHead;

之后，上述鏈表將變?yōu)槿缦聢D所示形式：

 [+]->[+]->[x]->[o]->[o]->[o]->[o]->[o]->[+]->[+]->^
       ^    ^                        ^
       |    |                        |
      tail revHead                revTail

如此反復(fù)多次，準(zhǔn)確的說是$n-m$次后，就可以完成翻轉(zhuǎn)了。
同時(shí)還需要注意的是$m==1$的情形。

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(n)$
空間復(fù)雜度：$O(1)$

代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* newHead = new ListNode(0);
        newHead->next = head;
        ListNode* tail = newHead;
        for (int i=0; i<m-1; ++i)
            tail = tail->next;
        ListNode* revTail = tail->next;
        ListNode* revHead = NULL;
        for (int i=0; i<n-m; ++i) {
            revHead = revTail->next;
            revTail->next = revHead->next;
            revHead->next = tail->next;
            tail->next = revHead;
        }
        // delete the pointer
        ListNode* toDelete = newHead;
        delete toDelete;
        newHead = newHead->next;
        return newHead;
    }
};

廣告區(qū)域

本人和小伙伴們承接各種軟件項(xiàng)目，有需求的可以聯(lián)系我們。
QQ: 2992073083