以恒定时间复杂度查找双向链表的中间元素

Question

我试图以常数时间复杂度找到双链表的中间元素。我遇到了以下 http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/ 解决方案。但是我不明白如何使用中间指针。任何人都可以帮助我理解这一点或给我一个更好的解决方案。

Answer 1

诀窍在于您不会通过搜索找到它，而是将其作为列表的属性不断维护。在你的link中，他们定义了一个结构体，包含头节点、中间节点和节点数；由于中间节点是一个属性的结构体，你可以随时直接访问return它。从那里开始，诀窍就是维护它：因此 push 和 pop 函数必须调整中间节点，代码中也显示了这一点。

更深入：维护中间节点：我们知道对于奇数个节点（比如 9）的计数，中间节点是 "number of nodes divided by 2 rounded up," 所以 9/2 = 4.5 四舍五入 = 第 5 个节点。因此，如果您从 8 个节点的列表开始，并添加一个节点，则新计数为 9，您需要将中间节点移动到 "next" 节点。这就是他们检查新计数是否偶数时所做的事情。

Answer 2

出于解释目的，我用 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”的列表。目前 mid 是 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 假设唯一的变化是节点的添加或删除，并且在添加或删除之前，mid 的位置是正确的。但是，我们通过将属性和函数 UpdateMiddle 设为私有并通过 public 函数使其可修改来确保这一点。

以恒定时间复杂度查找双向链表的中间元素

Find middle element of a double linked list in constant time complexity

linked-list