1

我知道如何表示链表的方式基本上是创建一个Node类（最好是struct），然后创建实际的linkedList类。然而，昨天我正在寻找反转单链表操作的逻辑，我遇到的几乎 90% 的解决方案都包括该函数，返回数据类型Node*。因此我很困惑，因为如果你想反转一个列表，不管你做了什么操作，它不会又是linkedList的类型吗？我做错了吗？

我一直在做的链表实现；

#include <iostream>
using namespace std;

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

class linkedList
{
public:
    Node* firstPtr;
    Node* lastPtr;

    linkedList()
    {
        firstPtr=lastPtr=NULL;
    }
    void insert(int value)
    {
        Node* newNode=new Node;
        newNode->data=value;
        if(firstPtr==NULL)
            firstPtr=lastPtr=newNode;
        else {
            newNode->next=firstPtr;
            firstPtr=newNode;
        }
    }
    void print()
    {
        Node *temp=firstPtr;
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
    }
};
4

3 回答 3

4

你的方法没有错，但你可能过分强调你的linkedList班级。

该类实际上包含什么？一个指向第一个节点的指针，一个指向最后一个节点的指针（这是冗余信息，因为您只需知道第一个节点就可以找到最后一个节点）。所以基本上linkedList只是一个没有额外信息的辅助类。

from 的成员函数linkedList可以很容易地移动到内部Node，或者将其作为自由函数，并将 aNode作为参数。

于 2012-04-23T08:50:02.817 回答
2

那么，除了指向第一个节点的指针之外，什么是链表？如果您可以到达第一个节点，则列表是完全可访问的，而您所需要的只是指向第一个节点的指针。

除非您想存储有关列表的额外控制信息（例如其长度），否则列表本身不需要单独的数据类型。

现在一些实现（比如你的）也可以存储指向列表中最后一个节点的指针以提高效率，允许你在 O(1) 而不是 O(n) 中追加一个项目。但这是列表的一个额外功能，而不是一般列表的要求。

于 2012-04-23T08:49:12.443 回答
0

这些函数可能返回 Node* 类型，因为在反转链表后，它们将返回指向链表第一个节点的指针。

于 2012-04-23T08:52:12.953 回答