在C++中反转双向链表

Question

在C++中反转双向链表

3

我一直在尝试弄清楚如何反转双向链表的顺序，但是由于某种原因，在我的函数void reverse()中，while循环只运行一次，然后出现崩溃。提前回答一些问题，我是自学的，有我兄弟的帮助。这不是所有的代码，但我有一个display()函数，它按照从start_ptr开始的时间顺序打印所有节点和一个开关，可以激活某些函数。

    case 1 : add_end(); break;
    case 2 : add_begin(); break;
    case 3 : add_index(); break;
    case 4 : del_end(); break;
    case 5 : del_begin(); break;
    case 6 : reverse(); break;

以下是我的代码要表达的要点：

#include <iostream>
using namespace std;

struct node
{
    char name[20];
    char profession[20];
    int age;
    node *nxt;
    node *prv;
};

node *start_ptr = NULL;

void pswap (node *pa, node *pb)
{
    node temp = *pa;
    *pa = *pb;
    *pb = temp;
    return;
}

void reverse()
{
    if(start_ptr==NULL)
    {
        cout << "Can't do anything" << endl;
    }
    else if(start_ptr->nxt==NULL)
    {
        return;
    }
    else
    {
        node *current = start_ptr;
        node *nextone = start_ptr;
        nextone=nextone->nxt->nxt;
        current=current->nxt;
        start_ptr->prv=start_ptr->nxt;
        start_ptr->nxt=NULL;
        //nextone=nextone->nxt;
        while(nextone->nxt!= NULL)
        {
            pswap(current->nxt, current->prv);
            current=nextone;
            nextone=nextone->nxt;
        }
        start_ptr=nextone;
    }
}

- Dan

2

你正在交换节点的内容而不仅仅是节点指针，你确定要这样做吗？ - Marius Gedminas

相关的是，你可以从不同的角度看待这些事情。与其反转双向链表本身的内容，不如专注于以相反的顺序迭代列表的内容，这应该很简单，因为列表是双向链接的。例如，为您的列表实现STL风格的双向迭代器。它们可以与std::reverse_iterator<>适配器一起使用（用于rbegin()和rend()）。一旦实现了这些方法，就很容易利用STL算法，包括std::reverse()。在我看来，这是一个有趣的练习。 - Void

10个回答

3

编辑：我的第一次实现是正确的，但不完美。 你的实现方式相当复杂。你可以尝试使用这个：

node * reverse(Node * start_ptr)
{
    Node *curr = start_ptr; 
    Node * prev = null;
    Node * next = null;
    while(curr)
    {
        next = curr->nxt;
        curr->nxt = prev;
    curr->prv = next;
        prev = curr;
        curr = next;
    }
    return start_ptr=prev;
}

这是我的更新方案：

node * reverse()
{
    node *curr = start_ptr; 
    node * prev = NULL;
    node * next = NULL;
    while(curr)
    {
        next = curr->nxt;
        curr->nxt = prev;
        curr->prv = next;
        prev = curr;
        curr = next;
    }
    return start_ptr=prev;
}

逻辑是正确的。但问题在于我接受了输入参数start_ptr。这意味着我返回的是它的本地副本。现在应该可以工作了。

- bits

我就是想不出我可能是怎么做到的。有人能确认一下这个实现是否创建了一个循环链表吗？谢谢... - bits

嗨，Danutenshu，我已更新了我的解决方案。我知道你的问题已经解决了，但如果你能告诉我我所做的更改是否正确，我会感觉好得多。 - bits

2

您可以将reverse()函数简化很多。我会这样做：

void reverse()
{
    if(start_ptr == NULL)
    {
        cout << "Can't do anything" << endl;
    }
    else
    {
        node *curr = start_ptr;
        while(curr != NULL)
        {
            Node *next = curr->next;
            curr->next = curr->prev;
            curr->prev = next;
            curr = next;
        }
        start_ptr = prev;       
    }
}

解释：基本思路就是访问每个Node并交换previous和next的链接。当我们将curr移动到下一个Node时，我们需要存储下一个节点，以便在将curr.next设置为prev时仍然有指向它的指针。

- Justin Ardini

我认为您忘记更新第一个节点的prev为第二个节点了。 - Borealid

确实，我一开始就错了一个。现在应该好了。 - Justin Ardini

1

简单的解决方案。在列表上的总迭代次数不到一半的情况下进行反转。

template<typename E> void DLinkedList<E>::reverse() {
    int median = 0;
    int listSize = size();
    int counter = 0;

    if (listSize == 1)
    return;

    DNode<E>* tempNode = new DNode<E>();

    /**
     * A temporary node for swapping a node and its reflection node
     */
    DNode<E>* dummyNode = new DNode<E>();

    DNode<E>* headCursor = head;
    DNode<E>* tailCursor = tail;

    for (int i = 0; i < listSize / 2; i++) {
        cout << i << "\t";

        headCursor = headCursor->next;
        tailCursor = tailCursor->prev;

        DNode<E>* curNode = headCursor;
        DNode<E>* reflectionNode = tailCursor;

        if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
            /**
             * insert a dummy node for reflection
         * for even sized lists
         */
        curNode->next = dummyNode;
        dummyNode->prev = curNode;

        reflectionNode->prev = dummyNode;
        dummyNode->next = reflectionNode;

    }
    /**
     * swap the connections from previous and 
             * next nodes for current and reflection nodes
     */

    curNode->prev->next = curNode->next->prev = reflectionNode;

    reflectionNode->prev->next = reflectionNode->next->prev = curNode;

    /**
     * swapping of the nodes
     */

    tempNode->prev = curNode->prev;
    tempNode->next = curNode->next;

    curNode->next = reflectionNode->next;
    curNode->prev = reflectionNode->prev;

    reflectionNode->prev = tempNode->prev;
    reflectionNode->next = tempNode->next;

    if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
        /**
         * remove a dummy node for reflection
         * for even sized lists
         */
        reflectionNode->next = curNode;
        curNode->prev = reflectionNode;
    }

    /**
     * Reassign the cursors to position over the recently swapped nodes
     */
        tailCursor = curNode;
        headCursor = reflectionNode;

    }

    delete tempNode, dummyNode;
}

template<typename E> int DLinkedList<E>::size() {
    int count = 0;
    DNode<E>* iterator = head;

    while (iterator->next != tail) {
        count++;
        iterator = iterator->next;
    }
    return count;
}

- Hussain Pithawala

0

我建议保持与最后一个节点的链接。
如果没有，请找到最后一个节点。使用“previous”链接（或在您的情况下，prv）遍历列表。

实际上不需要改变链接。使用prv指针遍历将自动以相反的顺序访问节点。

- Thomas Matthews

0

我想在这里添加一个递归解决方案。

node* reverse_and_get_new_head(node* head) {
    if (head == nullptr) { return nullptr; } 
      // This can be avoided by ensuring the initial,
      // outer call is with a non-empty list
    std::swap(head->prev, head->next);
    if (head->prev == nullptr) { return head; }
    return reverse_and_get_new_head(head->prev);
}

void reverse() {
    start_ptr = reverse_and_get_new_head(start_ptr);
}

- einpoklum

0

我反转双向链表的代码：

Node* Reverse(Node* head)
{
// Complete this function
// Do not write the main method. 


if(head != NULL) {

    Node* curr = head;
    Node* lastsetNode = curr;
    while(curr != NULL) {

        Node* frwdNode = curr->next;
        Node* prevNode = curr->prev;


        if(curr==head) {                
            curr->next = NULL;
            curr->prev = frwdNode;
            lastsetNode = curr;
        }
        else {
            curr->next = lastsetNode;
            curr->prev = frwdNode;
            lastsetNode = curr;
        }



        curr = frwdNode;
    }

    head = lastsetNode;
}


return head;
}

- Ashish

0

一个非常简单的O(n)解决方案，使用两个指针：

start = 双向链表的头部

struct node *temp, *s;
s = start;

while(s != NULL){
  temp = s->prev;
  s->prev = s->next;
  s->next = temp;
  s = s->prev;
}

//if list has more than one node
if(current != NULL){
  start = temp->prev;
}

- Jyo the Whiff

0

你的pswap函数有问题，应该交换指针而不是尝试创建临时对象并交换它们。应该像这样（后面可能还有其他错误）：

void pswap (node *&pa, node *&pb)
{
    node* temp = pa;
    pa = pb;
    pb = temp;
    return;
}

- mb14

那样实际上什么也做不了。你需要传递指向指针或指向指针的引用，这样更改才会应用于原始对象，而不是本地副本。 - SoapBox

你说得完全正确，我没有看函数签名。只是修复了临时对象创建的错误。 - mb14

0

看一下

valuesnextone=nextone->nxt->nxt;

这里的nextone->nxt可能为空。

除此之外，在交换函数中尝试使用指向指针的指针。

- Diego Pereyra

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Borealid · Accepted Answer

7

试试这个：

node *ptr = start_ptr;
while (ptr != NULL) {
    node *tmp = ptr->nxt;
    ptr->nxt = ptr->prv;
    ptr->prv = tmp;
    if (tmp == NULL) {
        end_ptr = start_ptr;
        start_ptr = ptr;
    }
    ptr = tmp;
}

- Borealid

最好的一个，尽管我有点脑抽，因为你没有以指向NULL的指针结束列表。 - Dan

哇，非常感谢你，我稍微修改了你的代码，它看起来比我所有之前尝试的代码都漂亮多了。你所需要做的就是在 start_ptr==NULL || start_ptr->nxt==NULL 处添加一个限定条件，并将你的部分作为 else 的结束。在此基础上，我确保在代码结尾处增加了 end_ptr->nxt=NULL; 。非常感谢！ - Dan

我不太确定为什么你需要那些检查 - 我认为我给出的代码在没有它们的情况下也能正常工作。而且最后，end_ptr->nxt将是NULL，因为在开始时，start_ptr->prv是NULL。但无论如何，你很欢迎。 - Borealid

@Borealid，我们能不能将head指针赋值为最后一个节点，并将起始节点的prv赋值为NULL？ - roottraveller

@Dan：我知道已经过去了9年，但是end_ptr没有在任何地方定义。你做了这个更改吗？ - einpoklum