C++ 链表反向函数触发无限循环

Question

我从一个数组创建了一个链表。它工作正常。但是当我尝试使用 reverseList() 函数反转列表时，它会启动一个无限循环。当我尝试显示列表时，它重复显示最后两个成员。

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

struct node
{
    int data;
    struct node *next;
};

node *reverseList(node *h)
{
    node *p, *q, *r;
    p = h->next;
    q = h;
    r = NULL;
    while (p)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    h = q;
    return h;
}

int main()
{
    struct node *n, *h, *t;
    int arr[] = {2, 5, 9, 6, 8};
    n = new node;
    t = n;
    h = n;
    n->data = arr[0];

    for (int i = 1; i < 5; i++)
    {
        n = new node;
        n->data = arr[i];
        t->next = n;
        t = n;
    }
    n->next = NULL;
    node *p = reverseList(h);
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }

    return 0;
}

Answer 1

函数内 reverseList

node *reverseList(node *h)
{
    node *p, *q, *r;
    p = h->next;
    q = h;
    r = NULL;
    while (p)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    h = q;
    return h;
}

最初q->next指针指向的第一个节点h没有设置为nullptr。它仍然指向原始列表中的第二个节点。

就是在这条语句之后

q = h;

在 while 循环之前，指针 q->next 未设置为 nullptr。

如果传递的参数是空指针，函数也可以调用未定义的行为。

函数可以这样定义

node * reverseList( node *h )
{
    node *q = nullptr;

    for ( node *p = h; h != nullptr; p = h )
    {
        h = h->next;
        p->next = q;
        q = p;
    }

    h = q;

    return h;
}

或者最好使用更有意义的名称，例如

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

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

    return new_head;
}

注意，当列表不再需要时，您需要释放所有分配给列表的内存。

C++ 链表反向函数触发无限循环

C++ Linked List Reverse Function Triggers Infinite Loop

c++

reverse

linked-list

singly-linked-list

function-definition