C++中的反向双链表

Question

我一直在想如何颠倒双向链表的顺序，但由于某种原因，在我的函数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; 
    } 
} 

Answer 1

试试这个：

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; 
} 

Answer 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时，我们仍然有一个指向它的指针。

Answer 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。这意味着我正在返回它的本地副本。现在它应该工作。

Answer 4

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

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

Answer 5

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

没有必要实际改变周围的链接。使用prv指针遍历将自动以相反的顺序访问节点。

Answer 6

看

valuesnextone=nextone->nxt->nxt; 

这里nextone->nxt可以为空。

除此之外，尝试使用交换功能指针指针。

Answer 7

简单的解决方案。逆转小于一半以上的列表

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; 
} 

Answer 8

A中的数的总迭代的非常简单的，并使用两个指针O（n）的溶液：

开始=的双重LL

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; 
} 

Answer 9

头

我的代码用于反转双向链表，

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; 
}