我现在正在学校课间休息时练习指针,下面我写了一个方法来反转一个双链接列表,但是当我把它交给一个在线测试时,它失败了。

Node* Reverse(Node *head)
{
    int count = 0;
    struct Node *ptr = head;

    // return head if NULL
    if (head == NULL) {
        return head;
    }
    // if the list is only the head, then the reverse is just the head... so nothing changes
    if((head->next == NULL && head->prev == NULL)){
        return head;
    }

    //Come here if previous if statements fail, traverse the list until I reach tail which will become the
    // new head
    while(ptr->next != NULL){
        ptr = ptr->next;
        count++;
    }
    head = ptr; // this is the new head
    //starting from tail all the way to head swap the "prev" and "next" of each node
    struct Node *temp = ptr->next;

    for(int i = 0; i<count; i++){
        ptr->next = ptr->prev;
        ptr->prev = temp;
        ptr=ptr->next;
        temp= ptr->next;
        //count--;
    }

    return head;
}

我意识到,当我从头到尾遍历列表时,反转列表可能更明智,但我认为这很无聊,所以我决定从尾到头反转列表。我怀疑while循环或for循环中存在明显错误,但无法诊断该错误。

最佳答案

我认为错误就在这里:

while(ptr->next != NULL){
    ptr = ptr->next;
    count++;
}

假设你的链表中有两个元素。那么while循环将只迭代一次,count将是1。当您进入for循环时,它也只会迭代一次,这意味着您将正确地为新的head重新分配指针,而不是第二个元素(之前的head)。
如果将count初始化为1而不是0,则它应正确反映链接列表中元素的数量,并且for循环应正确执行。
编辑:您还需要稍微重新构造for循环,以避免列表末尾出现segfault:
Node* temp;

for (int i = 0; i < count; i++)
{
    temp = ptr->next;
    ptr->next = ptr->prev;
    ptr->prev = temp;
    ptr = ptr->next;
}

07-24 09:46
查看更多