在C++中创建一个反向LinkedList从给定的 LinkedList

Question

我在从给定的链接列表以相反的顺序创建链接列表时遇到一些问题。

我有java背景，刚刚开始做一些C++。

你能检查一下我的代码并看看有什么问题吗？我猜我只是在操纵指针而不是创建任何新内容。

//this is a method of linkedlist class, it creates a reverse linkedlist
//and prints it

void LinkedList::reversedLinkedList()
{
    Node* revHead;

    //check if the regular list is empty
    if(head == NULL)
       return;

    //else start reversing
    Node* current = head;
    while(current != NULL)
    {
        //check if it's the first one being added
        if(revHead == NULL)
           revHead = current;

        else
        {
            //just insert at the beginning
            Node* tempHead = revHead;
            current->next = tempHead;
            revHead = current;
        }
        current = current->next;

     }//end while

     //now print it
     cout << "Reversed LinkedList: " << endl;

     Node* temp = revHead;
     while(temp != NULL)
     {
         cout << temp->firstName << endl;
         cout << temp->lastName << endl;
         cout << endl;

         temp = temp->next;
      }

}//end method

Answer 1

更简单的方法：遍历链表，保存上一个和下一个节点，然后让当前节点指向前一个节点：

void LinkedList::reversedLinkedList()
{
    if(head == NULL) return;

    Node *prev = NULL, *current = NULL, *next = NULL;
    current = head;
    while(current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // now let the head point at the last node (prev)
    head = prev;
}

Answer 2

Node* revHead;
// ...
while(current != NULL)
{
    //check if it's the first one being added
    if(revHead == NULL)

您不初始化revHead，但您使用它。
（我希望您已经清楚 revHead 是一个用于存储内存地址的局部变量，而不是存在于方法/过程之外的东西）

revHead 的存储类code> 是自动的（也称为本地作用域主体）。在C++ 中，当您进行这样的声明时，不能保证该值将为0。

（除非存储类是static类型或变量是global，如果没有提供其他值，它会自动初始化为0。您的情况是，变量具有 auto 类型的存储类，这意味着它是在函数中本地定义的，并且在声明局部变量时，如果不指定值，则该值是垃圾。接下来的 C++ 标准 C++0x 关键字 auto 有了新的含义）。

您的情况中的值是垃圾，这会使 if 失败。请在此处查看更多信息：链接

请记住

Node* revHead = NULL;

，也许您的代码的其他部分也可能出现类似的错误。

Answer 3

只需使用两个临时变量即可完成此操作。

Node* list::rev(Node *first)
{
    Node *a = first, *b = first->next;
    while(a->next!=NULL)
    {
        b = a->next;
        a->next = a->next->next;
        b->next = first;
        first = b;
    }
    return first;
}

另外，您可以使用递归来完成此操作。

Answer 4

另一种方法是首先遍历列表并将所有数据存储在堆栈中，然后创建一个新列表并从堆栈顶部插入数据。堆栈是 LIFO 将以相反的顺序为您提供数据，因此您将得到一个颠倒列表。

Answer 5

NODE * ReverseLinkedList(NODE * head){
    if (head == NULL)
        return NULL;

    NODE * previous = NULL;
    while (head != NULL) {
        // Keep next node since we trash the next pointer.
        NODE *next = head->pNext;
        // Switch the next pointer to point backwards.
        head->pNext = previous;
        // Move both pointers forward.
        previous = head;
        head = next;
    }
    return previous;
}

Answer 6

我不确定，但我认为你想要一个双向链表，其中节点有下一个和上一个。使用指向列表的外部指针将无法工作。您将不会获得前一个节点的地址。

如果不使用上面的方法与堆栈，这是一个很好的建议。

Answer 7

下面的示例使用递归来反转链接列表。我在面试时问了这个问题。这已经过测试并且有效。 ListElem 是节点。

void LinkList::reverse()
{
if(pFirst == NULL) return;
ListElem* current = pFirst;
revCur(NULL, current, NULL);
}

void LinkList::revCur(ListElem *prev, ListElem* current, ListElem* next)
{
 //   ListElem *prev = NULL, *current = NULL, *next = NULL;
 if ( current != NULL )
 {
     next = current->next;
     current->next = prev;
     prev = current;
     current = next;
     pFirst = prev;
     this->revCur(prev,current,next);
    }
}

Answer 8

上面是Link List的反转

void LinkList::rev()
{
    if(pFirst == NULL) return;

    ListElem *prev = NULL, *current = NULL, *next = NULL;
    current = pFirst;
    while(current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // now let the head point at the last node (prev)
    pFirst = prev;
}

Answer 9

  #include <stdint.h>
  /*
      this is a generic (structure agnostic) routine for reversing a singly linked list.
      1st argument is the memory address the structure is located at, and
      2nd argument is the memory address to this particular structure's NEXT member.
  */
  void *rsll(void *struct_address, void *next_address /*(void **)*/)
  {
    uint32_t offset, holder;
    offset = next_address - struct_address;

    void **p = struct_address, *progress = NULL;
    while(p)
    {
      void *b;
      holder = (uint32_t)p;
      holder += offset;
      p = (void**)holder; //&(N->next)
      b = *p; //(N->next)
      *p = progress; //(N->next)
      holder = (uint32_t)p;
      holder -= offset;
      p = (void**)holder; //N
      progress = p;
      p = b;
    }
    return progress;
  }

  #include <stdio.h>
  int
  main()
  {
    struct list_t
    {
      int integer;
      struct list_t *next;
    };
    struct list_t d = {40,NULL},
                  c = {30,&d},
                  b = {23,&c},
                  a = {10,&b};
    struct list_t *list;
    list = &a;
    list = rsll(list,&(list->next));
    while(list)
    {
      printf("%d\n",list->integer);
      list = list->next;
    }
    return 0;
  }

Answer 10

我使用类的反向链表的完全可执行解决方案，因为人们发现的大多数示例仅使用结构：

#include <iostream>
#include <string>

class listElement
{
    std::string data;
    listElement* next;
    listElement* last; //for doubly linked list

    void append(std::string);
    void displayElements();
    void reverseDisplayElements(listElement*);

    listElement* reverseList(listElement*);


public:
    listElement() = default;
    listElement(std::string newElement)
        :data(newElement)
        , next(nullptr)
        , last(this)
    {}
    listElement &operator=(const listElement& other) = default;
    ~listElement();

    void setElement(std::string element){append(element);}
    void getElements();
    void getElementsReverse(listElement* elements);

    listElement* setElementsInReverseOrder(listElement* elements);
};

listElement::~listElement()
{
    //If the end is not reached, call the method again
    if (next != nullptr)
    {
        next->~listElement();
        delete(next);
    }
}

void listElement::getElements()
{
    std::cout << "\nPrint list:" << std::endl;
    displayElements();
}

void listElement::getElementsReverse(listElement *elements)
{
    std::cout << "\nJust print the list in reverse order:" << std::endl;
    reverseDisplayElements(elements);
}

listElement *listElement::setElementsInReverseOrder(listElement *elements)
{
    std::cout << "\n...Reversing elements..." << std::endl;
    return reverseList(elements);
}

void listElement::append(std::string newData)
{
    // Double linked list
    //    last->next = new listElement();
    //    last->next->data = newData;
    //    last->next->next = nullptr;
    //    last = last->next;

// Singly linked list
    //has next the value nullptr?
    //If yes, next pointer
    if (next == nullptr)
    {
        next = new listElement();
        next->data = newData;
        next->next = nullptr;
    }
    //else the method again
    else
        next->append(newData);
}

listElement* listElement::reverseList(listElement* head)
{
    //return if no element in list
    if(head == nullptr)
        return nullptr;

    //initialize temp
    listElement* temp{};

    while(head != nullptr){
        listElement* next = head->next;
        head->next = temp;
        temp = head;
        head = next;
    }
    return temp;
}

void listElement::displayElements()
{
    //cout the first entry
    std::cout << data << std::endl;
    //if the end is not reached, call method next again
    if (next != nullptr)
        next->displayElements();
}

void listElement::reverseDisplayElements(listElement*head)
{
    //recursiv from the last to the list beginning - stop
    listElement *temp = head;

    if(temp != nullptr)
    {
        if(temp->next != nullptr)
        {
            reverseDisplayElements(temp->next);
        }
      std::cout << temp->data << std::endl;
    }
}

int main ()
{
    //Pointer to the Beginning of the list
    listElement* linkedList = new listElement("Element 1");

    //add more elements
    linkedList->setElement("Element 2");
    linkedList->setElement("Element 3");
    linkedList->setElement("Element 4");

    linkedList->getElements();
    linkedList->getElementsReverse(linkedList);
    linkedList->getElements();
    linkedList = linkedList->setElementsInReverseOrder(linkedList);
    linkedList->getElements();

    return 0;
}

我对生产代码的建议是使用

std::list 因为它是一个链接列表

或 std::vector 如果您需要高效的数组实现。