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 回答