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