反转带值的双向链表

Question

我目前无法获得双向链表的反向函数以正确处理作业，我已经阅读了其他线程并在 google 上进行了搜索，但通常不同的是我的问题通过了在常数并且它 returns 是 "dlist"。教授提供了一个 "code tester"，它说我的代码在执行 "reverse(reverse(dlist c))" 时不等于它本身是 "c"。 [倒转两次不等于自己]。

dlist class 是：

class dlist {
public:
dlist() { }
int sizeOfDlist =0; // To keep track of size 
struct node {
    int value;
    node* next;
    node* prev;
};

node* head() const { return _head; } // _head = beginning of list
node* tail() const { return _tail; } // _tails = end of list
node* _head = nullptr;
node* _tail = nullptr;

这里是反向函数：

dlist reverse(const dlist& l){
if(l._head == nullptr||l._tail ==nullptr){ // Checks if l list is empty
    dlist newRList;
    return newRList;//return a blank list;
}

if(l.head()!=nullptr){
    dlist::node* temp;
    dlist::node* ptr1 = l._head;
    dlist::node* previous = nullptr;

    while(ptr1 != nullptr){
        temp = ptr1->next;
        ptr1->next = previous;
        previous = ptr1;
        ptr1 = temp;
    }
    dlist newRList;
    newRList._head = previous;
    return newRList;
   }
else //if something passes by, return original list
    return l;
}

每个dlist节点都有一个指向前一个节点的指针和一个指向下一个节点的指针。 dlist 节点还包含一个 int 值。

我试图实现的是创建一个从原始列表的 "tail" 开始或结束的列表。然后列表将倒退并交换 "next" 和 "prev" 指针。我做错了什么？

已解决： 通过使用 push_front 函数将值添加到列表的前面并将其他所有内容推到它后面，我能够获取值从给定的常量 dlist 和 push_front 所有值到 "newRList" 中，这颠倒了顺序。

感谢 user4581301 和 Basya Perlman 的帮助，这是新的反向功能：

dlist reverse(const dlist& l){
if(l._head == nullptr||l._tail ==nullptr){ // Checks if l list is empty
    dlist newRList;
    return newRList;//return a blank list;
}

if(l.head()!=nullptr){
   dlist newRList;
   for(int n=0; n<l.size(); n++){ // Size function checks the size of the doubly linked list 

       newRList.push_front(l.valueGetter(n)); // Value Getter is a function that grabs the value at a specific [iteration], push_front pushes said value into the front of the list.
    }
    return newRList;
}
else //if something passes by, return original list 
    return l;
}

Answer 1

您的反向函数看起来像是设置为 return 一个新的 dlist。它 return 是一个对象，而不是指针或引用。

此外，您的参数是一个 const dlist，但您正试图就地反转它，然后将一个新指针指向列表的头部并 return 那个。然后测试人员将 returned 列表与原始列表进行比较；但是原来的列表，本来是 const，但被修改了？我有点糊涂了，所以也许电脑运行你的程序太:-)

从函数定义来看，其思路似乎是通过将元素倒序复制到新列表中来创建一个新列表，并保持原始列表不变。在您的评论中，您有一个 push_back 和一个 push_front 函数；您可以向前循环遍历现有列表并将每个元素的副本 push_front 复制到新列表中，以将其反转（是否需要明确制作副本取决于 push_front 函数的定义，我没有）。

反转带值的双向链表

Reversing a Doubly-Linked List with Values

c++

reverse

doubly-linked-list