为什么这个函数不能反转链表？

Question

我想反转链表，但是当我编译这段代码时它意外终止。

#include <bits/stdc++.h>
using namespace std;

class node{
public:
    int data;
    node* next;

    node(int val){
    data=val;
    next=NULL;
        }
};

用于在链表中插入元素

void insertattail(node* &head,int lol){
    node* n= new node(lol);
    if(head==NULL){
        head=n;
        return;
    }
    node* temp=head;
    while(temp->next!=NULL){
        temp=temp->next;
    }
    temp->next=n;
}

显示函数打印链表

void display(node* head){
    node* temp =head;
    do{
        cout<<temp->data<<"->";
        temp=temp->next;
    }
    while(temp!=NULL);
    cout<<"Null";

}

反转链表的函数

node* reverseit(node* head){
    node* prevptr= NULL;
    node* currptr= head;
    node* nextptr= currptr->next;
    while(currptr!=NULL){
        currptr->next =prevptr;
        prevptr=currptr;
        currptr=nextptr;
        nextptr=currptr->next;
    }
    return prevptr;
}

主要功能

int main()
{
    node* head= NULL;
    insertattail(head,1);
    insertattail(head,2);
    insertattail(head,3);
    insertattail(head,8);
    node* newhead= reverseit(head);
    display(newhead);
    return 0;
}

我认为问题出在反向函数的逻辑上。我只是使用链表的代码并做了一些小改动。

Answer 1

该函数调用了未定义的行为。

例如，我们首先假设列表是空的。即指针head等于nullptr。在这种情况下，在函数

的 while 循环之前使用这一行

node* nextptr= currptr->next;

使用空指针访问内存。

或者让我们考虑另一个例子，当 current->next 等于 nullptr 时。在这种情况下 nextptr 将等于 nullptr 并且在 while 循环中这些语句

    currptr=nextptr;
    nextptr=currptr->next;

再次使用空指针访问内存。

以及while循环之前的许多指针声明

node* prevptr= NULL;
node* currptr= head;
node* nextptr= currptr->next;

使代码的可读性和清晰度降低。

函数可以这样定义

node * reverseit( node *head )
{
    node *new_head = nullptr;

    for ( node *current = head; head != nullptr; head = current )
    {
        current = head->next;
        head->next = new_head;
        new_head = head;
    }

    return new_head;
}

如果您的程序实际上是 C 程序，那么请使用 NULL.

而不是 nullptr

同样在main中不需要引入新的指针newhead

node* newhead= reverseit(head);

你可以直接写

head = reverseit(head);

如果传递给头节点的指针等于 nullptr，函数 display 可以再次调用未定义的行为。并且函数的参数应该有限定符 const 因为在函数中列表本身没有改变。

函数可以这样定义

std::ostream & display( const node *head, std::ostream &os = std::cout )
{
    for ( const node *current = head; current != nullptr; current =current->next )
    {
        os << current->data << " -> ";
    }

    return os << "Null";
}

而且函数可以这样调用

display( head ) << '\n';

Answer 2

您的初始化和 nextptr 的 'incrementing' 都 (potentially/eventually) 取消引用 currptr 的 NULL 值。您应该将 nextptr 初始化为 NULL，并且仅当 currptr 不是 NULL 时才将其更改为 'real'；因此，它的（重新）分配应该在循环的 start 处，而不是在 end:

node* reverseit(node* head){
    node* prevptr = nullptr;
    node* currptr = head;
    node* nextptr = nullptr; // Don't assume a non-NULL currptr
    while (currptr != nullptr) {
        nextptr = currptr->next; // Safe here: save next
        currptr->next = prevptr; // Do the reversal here
        prevptr = currptr;       // Step forward through
        currptr = nextptr;       // the list (prev/curr)
    //  nextptr = currptr->next; // WRONG HERE: currptr will be NULL at some point
    }
    return prevptr;
}

为什么这个函数不能反转链表？

Why this function is not able to reverse the Linked List?

c++

reverse

struct

singly-linked-list

function-definition