92. Reverse Linked List II - better solution

難度: Medium

類型: Linked List

CPP程式下載: 92_2.cpp

前情題要:

反向連結 --- 給定一個連結的 list, 一個左邊位址, 一個右邊位置, 左邊位置小於或等於右邊位置, 把這個連結的左邊位置到右邊位置的連結反向, 回傳結果。(能夠一輪就給答案嗎?)

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?

思考方式:

stack 的先進後出特性, 剛好拿來做反向連結。

1. 為了不破壞原有的 link list, 所有 output link list 的成員都是 new 出來的。這種方式會花費比較多的記憶體空間。其實也有另一種方法是直接改在原本的 linked list 上, 有機會另一篇文章再寫。

2. 運算過程中, 在大於等於左邊位置, 卻還仍小於右邊位置之前, 這些 linked list 的成員都 push 進Stack裡, 直到等於右邊位置時, 把右邊位置的 linked list 放上output連結後, 把 stack 裡的內容一個一個 pop 出來, 直到 stack 為空。

3. 記得更新 input linked list pointer 與 output linked list pointer。每次設定完一個新的output成員後, 記得把 output pointer 指定到 next。

======================================

原本上面的方式並沒有不好....甚至某些情況下, 並不允許對 input linked list 改動, 那就只能照原本的方法做。

但就如前面所說, 這會多new出一組的 linked list, 占用比較多的記憶體空間。下面就是介紹操作原本的 linked list, 把 link 切斷, 反轉, 再重組的方式。

A. linked list 在到達 left 位置前, 都沒變。

B. 到 left 位置之後, 前一個位置的next連結就要跟 left 這個 ListNode 斷開, 之後要連到 right 位置的 ListNode。所以left position的前一個位置上的 ListNode 位置要儲存起來。(ListNode *pPreLeftNode)

C. left 位置的 ListNode 也是要等處理到 right 位置, 把自身的 next 改為原本 right 位置 ListNode 的 next。 (ListNode *pLeftNode)

D. 因為從 left 到 right 位置的連結要反向, 所以處理到某個left 到 right 之中的位置時, 目前位置的 ListNode -> next 會需要設前一個位置的 ListNode, 這時候 next 位置的連結會被蓋掉, 所以在下一個位置的連結被蓋掉之前也要存起來。如此一來就需要存前一個位置的 ListNode (pPreNode), 下一個位置的 ListNode (pNextNode), 還有為了好操作, 也要一個目前位置的 ListNode (pCurNode)。

E. 目前的位置的 next 都會被改, 所以用 next ListNode 的 next (pNextNode=pNextNode->next) 來取得下一個連結的 ListNode。然後目前位置的操作結束後, 把下個再下個連結當成下一輪的 next LinkNode, 下一個連結變成目前的連結, 目前的連結變成前一個連結。

F. 處理完 right 位置的設定之後, 把 pPreLeftNode -> next 設到 right 位置的 ListNode, 再把 pLeftNode -> next 設到 pNextNode, 到這邊就大功告成, right position 後面的連結都不會變, 因此現在就可以回傳 output 的 linked list 了。

G. 注意邊界: 要注意 Left  有可能是頭, 這樣的話就沒有pPreLeftNode。記得 output 從 right 位置的 ListNode 開始。同樣道理, 如果 Right position 是Linked List的最後一個, 那 Left position 的 ListNode 就是 output linked list 中的最後一個。

H. 注意 left 可能跟 right 相同, 那樣就不必倒轉連結, output 就跟 input listed list 一樣。

複雜度思考:

Time Complexity: Worst case: O( N )

Space Complexity: O( 5 個 ListNode的指標變數 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 11.10 MB, Beats: 96.21%

Accepted

44 / 44 testcases passed

tendchen

submitted at Nov 08, 2025 08:08

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

11.10MB

Beats96.21%

Analyze Complexity

Code

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *pPreLeftNode; //its next ptr has to change to pRightNode
        ListNode *pLeftNode; //its nextNode -> next has to point this back
        ListNode *pCurNode;
        ListNode *pNextNode=nullptr;
        ListNode *pPreNode;
        int i;
        pCurNode=head;
        // loop till current Node -> next is null.
        if (left==1)
        {
            if (right==1)
            {
                return head;
            }
            else
            {
                pLeftNode=pCurNode;
                pPreNode=pCurNode;
                pCurNode=pCurNode->next;
                if (pCurNode!=nullptr)
                {
                    pNextNode=pCurNode->next;
                }
                else
                    pNextNode=nullptr;
                //pCurNode -> next -> next = pCurNode;
                //pCurNode = pCurNode -> next;
                for (i=2;;i++)
                {
                    if (i==right)
                    {
                        pLeftNode -> next = pNextNode;
                        pCurNode -> next = pPreNode;
                        return pCurNode;
                    }
                    else
                    {
                        pCurNode -> next = pPreNode;
                        pPreNode = pCurNode;
                        pCurNode = pNextNode;
                        if (pNextNode!=nullptr)
                            pNextNode = pNextNode -> next;
                    }
                }
            }
        }
        for (i=1;;i++)
        {
            //cout << "i=" << i << "\n";
            //cout << "pCurNode->val=" << pCurNode->val << "\n";
            if (i<left)
            {
                if (i==(left-1))
                {
                    pPreLeftNode=pCurNode;
                    pPreNode=pCurNode;
                    pNextNode=pCurNode->next->next;
                    pCurNode=pCurNode->next;
                    
                }
                else
                {
                    pCurNode=pCurNode->next;
                    //continue;
                }
            }
            else if (i==left)
            {
                if (i==right)
                {
                    return head;
                }
                else
                {
                    pLeftNode=pCurNode;
                    pPreNode=pCurNode;
                    pNextNode=pCurNode->next->next;
                    pCurNode=pCurNode->next;
                }
            }
            else
            {
                if (i==right)
                {
                    //cout << "pPreNode->val=" << pPreNode->val << "\n";
                    //cout << "pCurNode->val=" << pCurNode->val << "\n";
                    pPreLeftNode->next=pCurNode;
                    pLeftNode->next=pNextNode;
                    pCurNode->next=pPreNode;
                    return head;
                }
                else
                {
                    //cout << "pPreNode->val=" << pPreNode->val << "\n";
                    //cout << "pCurNode->val=" << pCurNode->val << "\n";
                    pCurNode->next=pPreNode;
                    pPreNode=pCurNode;
                    pCurNode=pNextNode;
                    pNextNode=pNextNode->next;
                }
            }
        }
    }
};