在恆定時間複雜度中查找雙鏈表的中間元素

Question

我想在常量時間複雜度中找到雙鏈表的中間元素。 我碰到以下http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/解決方案。 但我不明白如何使用中間指針。 任何人都可以請幫我理解這個或給我一個更好的解決方案。

Answer 1

我已經重新用C++編寫的代碼的解釋用途：

#include <iostream> 

typedef class Node* PNode; 
class Node{ 
public: 
    PNode next; 
    PNode prev; 
    int data; 
    Node(){ 
     next = nullptr; 
     prev = nullptr; 
     data = 0; 
    } 
}; 

class List{ 
private: 
    //Attributes 
    PNode head; 
    PNode mid; 
    int count; 
    //Methods 
    void UpdateMiddle(bool _add); 

public: 
    //Constructors 
    List(){ 
     head = nullptr; 
     mid = nullptr; 
     count = 0; 
    } 
    ~List(){ 
     while(head != nullptr){ 
      this->delmiddle(); 
      std::cout << count << std::endl; 
     } 
    } 
    //Methods 
    void push(int _data); 
    void pop(); 
    int findmiddle(); 
    void delmiddle(); 
}; 

void List::UpdateMiddle(bool _add){ 
    if(count == 0){ 
     mid = nullptr; 
    } 
    else if(count == 1){ 
     mid = head; 
    } 
    else{ 
     int remainder = count%2; 
     if(_add){ 
      if(remainder == 0){ 
       mid = mid->prev; 
      } 
     } 
     else{ 
      if(remainder == 1){ 
       mid = mid->next; 
      } 
     } 
    } 
} 

void List::push(int _data){ 
    PNode new_node = new Node(); 

    new_node->data = _data; 
    new_node->prev = nullptr; 
    new_node->next = head; 

    if(head != nullptr) head->prev = new_node; 
    head = new_node; 
    count++; 

    UpdateMiddle(true); 
} 

void List::pop(){ 
    if(head != nullptr){ 
     PNode del_node = head; 
     head = head->next; 

     if(head != nullptr) head->prev = nullptr; 

     delete del_node; 
     count--; 
     UpdateMiddle(false); 
    } 
    else if(count != 0){ 
     std::cout << "ERROR"; 
     return; 
    } 
} 

int List::findmiddle(){ 
    if(count > 0) return mid->data; 
    else return -1; 
} 

void List::delmiddle(){ 
    if(mid != nullptr){ 
     if(count == 1 || count == 2){ 
      this->pop(); 
     } 
     else{ 
      PNode del_mid = mid; 
      int remainder = count%2; 

      if(remainder == 0){ 
       mid = del_mid->next; 
       mid->prev = del_mid->prev; 
       del_mid->prev->next = mid; 
       delete del_mid; 
       count--; 
      } 
      else{ 
       mid = del_mid->prev; 
       mid->next = del_mid->next; 
       del_mid->next->prev = mid; 
       delete del_mid; 
       count--; 
      } 
     } 
    } 
} 

的push和pop功能是不言自明的，它們增加在堆棧的頂部節點，並刪除頂部的節點。在此代碼中，每當添加或刪除節點時，功能UpdateMiddle負責管理mid指針。它的參數_add告訴它一個節點是否已被添加或刪除。當有兩個以上的節點時，這個信息很重要。

請注意，當在push或pop內調用UpdateMiddle時，計數器已分別增加或減少。我們從基本情況開始，其中有0個節點。 mid將只是一個nullptr。當有一個節點時，mid就是那個節點。

現在讓我們看看數字「5,4,3,2,1」的列表。目前中間是3和count，節點數量是5個奇數。現在我們來添加一個6.現在將是「6,5,4,3,2,1」，count現在是6個偶數。 mid現在也應該是4，因爲它是中間的第一個，但它還沒有更新。但是，現在如果我們添加7將是「7,6,5,4,3,2,1」，count將是7，奇數，但注意mid不會改變，它應該仍然是4。

一個模式可以從中觀察到。當添加節點時，count從偶數變爲奇數，mid保持不變，但從奇數變爲偶數mid更改位置。更具體地說，它向左移動一個位置。這基本上是UpdateMiddle所做的。通過檢查count目前是否爲奇數或者甚至在添加或刪除節點之後，它決定mid是否應該重新定位。確定節點是否被添加或刪除也很重要，因爲在刪除時，邏輯與添加相反。這基本上是在您鏈接的代碼中應用的邏輯。

此算法的工作原理是因爲mid的位置在添加或刪除之前應始終爲正確的，並且功能UpdateMiddle假定唯一的更改是添加或刪除節點，並且在添加或刪除該位置之前，位置中期是正確的。但是，我們通過將屬性和功能UpdateMiddle保密，並通過公共功能對其進行修改來確保這一點。

Answer 2

訣竅是你不要找到它通過搜索，而不是你不斷維護它作爲列表的屬性。在你的鏈接中，他們定義了一個包含頭節點，中間節點和節點數量的結構;由於中間節點是該結構的屬性，因此您可以通過直接在任何時候直接訪問它來返回它。從那裏，訣竅是維護它：所以push和pop函數必須調整中間節點，這也顯示在代碼中。我們知道，對於奇數個節點（比如說9），中間節點是「節點數除以2的整數」，所以9/2 = 4.5向上取整=第5個節點。因此，如果您從8個節點列表開始，添加一個節點，則新計數爲9，您需要將中間節點移至「下一個」節點。這就是他們在檢查新計數是否均勻時所做的。