从尾到头反转双向链表

Question

我最近在放学练指针，下面写了一个双向链表反转的方法，交到网考时失败了。

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 循环有明显的错误，但我无法诊断错误。

Answer 1

我认为错误在这里：

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

假设您的链表中有 2 个元素。那么 while 循环只会迭代一次，而 count 将为 1。当你进入 for 循环时，它也只会迭代一次，这意味着你将正确地重新分配新头的指针，但不是第二个元素（以前的头）。

如果将 count 初始化为 1 而不是 0，它应该正确反映链表中元素的数量并且 for 循环应该正确执行。

编辑： 您还必须稍微重组 for 循环以避免列表末尾出现段错误：

Node* temp;

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

Answer 2

替换

for(int i = 0; i<count; i++){//i<count --> i<=count : Because Not counting last element
    ptr->next = ptr->prev;
    ptr->prev = temp;
    ptr=ptr->next;
    temp= ptr->next;//<-- bad
    //count--;
}

与

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

或

while(ptr){
    ptr->next = ptr->prev;
    ptr->prev = temp;
    temp = ptr;//next prev
    ptr = ptr->next;
}

从尾到头反转双向链表

Reverse a Doubly Linked List From Tail to Head

c

pointers

reverse

doubly-linked-list