0

我正在用指针实现一个链表。
我需要反转链表，所以我写了 rotate(List &l)
但我没有得到我期望的结果。
由于输入是
0 1 2 3 4 5 6 7 8 9
我会期望
9 8 7 6 5 4 3 2 1 0
结果，但我得到
0 9 8 7 6 5 4 3 2 1

既然我找不到我做错了什么，你能指出我做错了什么吗？问题似乎从这里开始：（旋转）

while(end->next !=0){
       end = end->next;
    }

我到那里第一个节点是最后一个节点（因为 cout << end->d; 给我0而不是9）

#include<iostream>

using namespace std;

typedef class Node *List;
struct Node{ 
    int d;
    List next;
};
//update : renamed
void reverse(List &l){
/*
start :
a b c d e

b c d e **a**
c d e **b** a
d e **c** b a
Result:
e **d** c b a
    */

    // get last node
    List end = l;
    while(end->next !=0){
       end = end->next;
    }
    //insert first node directly after the original last node
    while(l!=end){
        List hulp = l;
        l = hulp->next;
        hulp->next = end->next;
        end->next=hulp;
    }
}
int main(){
    List l = new Node();
    int i = 0;
    List k = l;
    while (i < 10)
    {
        k->d = i;
        k->next = new Node();
        k = k->next; 
        i++;
    }
    List m = l;
    while ( m->next !=0 )
    {
        cout << m->d << endl;
        m = m->next;
    }
    reverse(l);
     m = l;
    while ( m->next !=0 )
    {
        cout << m->d << endl;
        m = m->next;
    }
}
4

2 回答 2

3

这不是迭代链表的典型方式：

while (m->next != 0) {
    cout << m->d << endl;
    m = m->next;
}

相反，您应该这样做：

while (m != 0) {
    cout << m->d << endl;
    m = m->next;
}

如果你这样做，你会看到你最初创建的链表实际上是：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0

然后您的打印逻辑将其打印为：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

然后您的反向可能会正常运行，生成以下列表：

0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

您打印为：

0, 9, 8, 7, 6, 5, 4, 3, 2, 1
于 2013-01-25T01:41:48.970 回答
1

您错误地初始化了列表。d=9 的最后一个节点，它应该有一个 null next，但它实际上有一个new Node. 要解决此问题，请将列表初始化更改为：

for (int i = 0; ; ++i)
{
    k->d = i;
    if (i >= 9) {
        break;
    }
    k->next = new Node();
    k = k->next; 
}

更改后，您还需要更改初始和最终打印（否则您将不会打印最后一个节点）。打印代码应该是（你最好把它放到一个打印函数中以避免重复代码）：

for ( ; m; m = m->next)
{
    cout << m->d << endl;
}
于 2013-01-25T01:44:35.690 回答