使用getchar()读取数字后链表存储顺序反转的问题排查

我用getchar()读取输入的数字，输入1234后，链表中存储的却是4、3、2、1。我怀疑问题出在getchar()或者类的某个函数里，但找不到具体位置。
Link类负责链表的删除、插入等操作，Node类负责节点的创建与赋值。
Creatlist函数负责链表的创建，是问题的主要来源，我在里面加了调试语句，可以运行查看结果。

using namespace std;

class Node
{
public:
    int data;
    Node *next;
    Node()
    {
        next = nullptr;
    }
    Node(int data)
    {
        this->data = data;
    }
    Node(const Node &temp)
    {
        this->data = temp.data;
    }
};

class Link
{
public:
    Node *head;
    int length = 0;
    Link()
    {
        head = new Node();
    }
    ~Link()
    {   
        while (head != nullptr)
        {
            Node *p = head->next;
            free(head);
            head = p;
        }
    }
    void insert(const Node &cache)
    {
        Node *temp = new Node(cache);
        temp->next = head->next;
        head->next = temp;
        length++;
    }
};

void Creatlist(Link &link) 
{
    char cache;
    while (1)
    {
        cache = getchar();
        if (cache == '\n')
            break;
        link.insert(Node(cache - '0'));
        cout << cache << " ";
    }
    cout<<endl;
    Node *p = link.head->next;
    cout << "in the linklist:";
    while (p != nullptr)
    {
        cout << p->data << " ";
        p = p->next;
    }
}

int main()
{
    Link link;
    cout<<"inut numbers:"<<endl;
    Creatlist(link);
}

问题原因 #

和getchar()无关，问题出在Link类的insert方法采用了头插法：
当你输入1234时，getchar()会按顺序读取'1'、'2'、'3'、'4'，但每次调用insert时，新节点都会被插到链表的最前面：

• 插入'1'后，链表：[1]
• 插入'2'后，链表：[2, 1]
• 插入'3'后，链表：[3, 2, 1]
• 插入'4'后，链表：[4, 3, 2, 1]

解决方法 #

方法1：改为尾插法（推荐） #

修改Link类，添加尾指针来实现尾插，同时修正析构函数的内存释放错误（用new创建的对象必须用delete释放，不能用free）：

class Link
{
public:
    Node *head;
    Node *tail; // 新增尾指针
    int length = 0;
    Link()
    {
        head = new Node();
        tail = head; // 初始时尾指针指向头节点
    }
    ~Link()
    {   
        while (head != nullptr)
        {
            Node *p = head->next;
            delete head; // 替换free为delete
            head = p;
        }
    }
    void insert(const Node &cache)
    {
        Node *temp = new Node(cache);
        temp->next = nullptr; // 确保新节点next为空
        tail->next = temp; // 新节点接在尾节点后
        tail = temp; // 更新尾指针
        length++;
    }
};

同时建议修正Node类带参数的构造函数，初始化next指针：

Node(int data)
{
    this->data = data;
    this->next = nullptr; // 避免野指针
}

方法2：头插后反转链表 #

如果坚持使用头插法，可以在Creatlist函数读取完所有字符后，调用链表反转函数，将顺序调整回来。

内容的提问来源于stack exchange，提问作者Constantine Marx