时间戳

首页 > 解决方案 > c++ 在不改变原始链表的情况下反转链表

c++ - c++ 在不改变原始链表的情况下反转链表

问题描述

我正在尝试反转链表，但我不想更改通过引用传入的原始链表，我该如何解决？

typedef Node * ListType 

ListType reverse(ListType list) {
   if (list == NULL) {
      return list;
   }
   ListType curr = list;
   //printList(list);               //list unchanged 
   ListType prev=NULL, next=NULL;
   while (curr != NULL) {     
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;  
   }
   //printList(list);              //list changed(I dont't want it changed)
   return prev;
}

标签： c++

解决方案

由于您不想更改原始列表，因此您必须对其进行复制。遍历原始列表，将新节点添加到反向列表中，然后返回它。

例如：

typedef Node* ListType;

ListType reverse(ListType list) {
    if (!list) {
        return NULL;
    }
    //printList(list); //list unchanged
    ListType curr = list, head = NULL, tail = NULL, copy;
    ListType *n = &tail;
    do {
        copy = new Node;
        copy->prev = NULL;
        copy->next = head;
        copy->data = curr->data; // copy your data field(s) as needed...
        *n = copy;
        n = &(copy->prev);
        head = copy;
        curr = curr->next;
    }
    while (curr);
    //printList(list); //list still unchanged
    return head;
}

只要确保调用者在使用它后释放返回的列表。

推荐阅读