反轉鏈表中的子串列并重新連接原始頭部

我正在處理反向鏈接串列問題，您可以在鏈接串列結構中反轉子串列。子串列定義為您必須反轉的部分left。right當使用較小的鏈接串列（大小為 2）時，它作業正常，但是當使用 5 個左右的元素時，它開始失敗。這是因為（如示例中所示）我不太了解如何維護原始頭部并連接到我現在反轉的子串列。我已經嘗試過head->next = prev;，但這不起作用并導致 nullptr 記憶體訪問錯誤。

對這個資料結構很陌生，如果能深入了解我如何解決這個問題，我將不勝感激。

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode* dummy = new ListNode(0, head);
    ListNode* prev = nullptr;
    ListNode* current = head;
    int counter = 1;
    while (current != nullptr)
    {
        if (counter == left)
        {
            ListNode* lastKnownParent = current;
            ListNode* n = nullptr;
            while (counter <= right)
            {
                n = current->next;
                current->next = prev;
                prev = current;
                current = n;
                counter  ;
            }
            lastKnownParent->next = current;
        }
        else {
            counter  ;
            current = current->next;
        }
    }
    dummy->next->next = current;
    dummy->next = prev;
   
    return dummy->next;
    
}

較小尺寸的成功： input: [3,5] left = 1, right = 2: Output: [5,3]

較大尺寸失敗： input: [1,2,3,4,5] left = 2, right = 4: Output: [2,4,3,2,5]

uj5u.com熱心網友回復：

有幾個問題：

• 函式底部的行不好。他們硬編碼需要在串列的前兩個節點上發生一些更改，但是當例如必須在節點 4 和 6 之間發生反轉時，這是沒有意義的。所以應該洗掉這兩行：

  dummy->next->next = current;
  dummy->next = prev;
  

• 前面 的節點lastKnownParent必須更新其next指標，但問題是不再有對該節點的直接參考。我上面參考的陳述句可能是為了到達那個節點，但它必須相對于left位置來完成。

left=4為了說明出了什么問題，當我們有一個包含 8 個節點的串列并且兩個給定位置是和時，看看這個可視化right=6：

當到達left并進入回圈時，我們得到這個狀態：

                            lastKnownParent
dummy    head                   current   n
  ↓       ↓                       ↓       ↓ 
┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   
│ 0 ├──?│ 1 ├──?│ 2 ├──?│ 3 ├──?│ 4 ├──?│ 5 ├──?│ 6 ├──?│ 7 ├──?│ 8 │
└───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘   └───┘
                          
                          prev == nulltptr

當到達right時，回圈再進行一次迭代，然后回圈退出，導致這種狀態：

dummy    head               lastKnownParent     prev    current   n
  ↓       ↓                       ↓               ↓       ↓       ↓
┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
│ 0 ├──?│ 1 ├──?│ 2 ├──?│ 3 ├──?│ 4 │?──┤ 5 │?──┤ 6 │   │ 7 ├──?│ 8 │
└───┘   └───┘   └───┘   └───┘   └─┬─┘   └───┘   └───┘   └───┘   └───┘
                                  ▼
                                nullptr

然后，您的代碼正確地設定了next值為 4 ( lastKnownParent) 的節點指標：

dummy    head               lastKnownParent     prev    current   n
  ↓       ↓                       ↓               ↓       ↓       ↓
┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
│ 0 ├──?│ 1 ├──?│ 2 ├──?│ 3 ├──?│ 4 │?──┤ 5 │?──┤ 6 │   │ 7 ├──?│ 8 │
└───┘   └───┘   └───┘   └───┘   └─┬─┘   └───┘   └───┘   └─▲─┘   └───┘
                                  └───────────────────────┘

但是缺少一件事。仍然需要建立從節點 3 到節點 6 的鏈接。這似乎是您在函式的最后嘗試過的東西，但您不能假設它總是dummy->next->next需要更改。這取決于left，或者換句話說，它取決于lastKnownParent。問題是lastKnownParent指向需要此更新的節點的后繼節點。因此，請在初始化時lastKnownParent指向前任。然后您可以進行兩次更新（首先更新節點 4，然后更新節點 3）。然后它看起來像這樣：

dummy    head       lastKnownParent             prev    current   n
  ↓       ↓              ↓┌──────────────────────┐↓       ↓       ↓
┌───┐   ┌───┐   ┌───┐   ┌─┴─┐   ┌───┐   ┌───┐   ┌▼──┐   ┌───┐   ┌───┐
│ 0 ├──?│ 1 ├──?│ 2 ├──?│ 3 │   │ 4 │?──┤ 5 │?──┤ 6 │   │ 7 ├──?│ 8 │
└───┘   └───┘   └───┘   └───┘   └─┬─┘   └───┘   └───┘   └─▲─┘   └───┘
                                  └───────────────────────┘

為了能夠lastKnownParent更早地設定一個節點，例如，即使在第一次迭代中，您也可以在prev后面跟隨- 當尚未遇到時。currentleft

這是更正后的代碼，其中有一些更改的注釋：

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode* dummy = new ListNode(0, head);
    ListNode* prev = dummy; // prev follows behind current
    ListNode* current = head;
    int counter = 1;
    while (current != nullptr)
    {
        if (counter == left)
        {
            ListNode* lastKnownParent = prev; // one node earlier
            ListNode* n = nullptr;
            while (counter <= right)
            {

                n = current->next;
                current->next = prev;
                prev = current;
                current = n;
                counter  ;
            }
            // lastKnownParent is now one node earlier than in your code
            lastKnownParent->next->next = current;
            lastKnownParent->next = prev; // now the mutation is complete...
            break; // ... so we don't need to iterate the remaining nodes.
        }
        else {
            counter  ;
            prev = current; // prev follows behind current
            current = current->next;
        }
    }
    // Removed two statements here
    return dummy->next;
}

進一步改進

此代碼假定給定的位置是有效的。您可能希望對此進行改進，并確定當一個或兩個超出范圍或right小于left.

您可能還想想出更優雅的方法來解決這個挑戰。例如，您可以創建能夠：

• 逆一個完整的串列
• 將某個位置的串列拆分為兩個較小的串列。
• 將較小的串列連接成一個

這可能會導致代碼更具可讀性。

標籤：C 链表撤销

上一篇：在C 中將失敗代碼作為列舉回傳似乎使代碼冗長

下一篇：C 如何洗掉最后一個逗號？