用c++从给定的LinkedList中创建一个反向的LinkedList

I'm having some trouble create a linkedlist in reverse order from a given linkedlist.

我在创建一个linkedlist时遇到了一些麻烦。

I come from a java background, and just started doing some C++.

我来自java背景，刚开始做c++。

Can you check out my code and see what's wrong? I'm guessing I'm just manipulating pointer and not creating anything new.

你能检查一下我的代码，看看有什么问题吗?我猜我只是在操作指针，没有创建任何新的东西。

//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

9 个解决方案

#1

Easier one: Go through your linked list, save the previous and the next node and just let the current node point at the previous one:

简单一点:浏览你的链接列表，保存上一个和下一个节点，让当前节点指向上一个节点:

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

#2

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

You don't initialize revHead but you use it. (I hope it is already clear to you that revHead is a local variable used to store a memory address, and not something that exists outside the method/procedure)

你没有初始化revHead，但是你使用它。(我希望您已经知道revHead是用来存储内存地址的本地变量，而不是方法/过程之外的东西)

The Storage Class of revHead is automatic (aka in the local scope-body). In C++ when you do a declaration like that, there is not guarantee that the value will be 0.

revHead的存储类是自动的(在局部作用域体中)。在c++中，当您做这样的声明时，不能保证值为0。

(unless the storage class is of type static or the variable is global where it is automatically initialized to 0 if no other value is provided. In your case the variable has storage class of type auto which means it is locally defined in a function, and when declaring a local variable, without specifying a value, the value is garbage. Keep in mind that with the next C++ Standard C++0x the keyword auto has a new meaning).

(除非存储类的类型是静态的，或者变量是全局的，如果没有提供其他值，那么它将自动初始化为0。在您的例子中，该变量具有自动类型的存储类，这意味着它是在函数中本地定义的，当声明局部变量时，在不指定值的情况下，该值是垃圾。记住，随着下一个c++标准c++ 0x的出现，关键词auto有了一个新的含义)。

The value in your case is garbage which makes the if fail. See more Information here : Link

在您的案例中，值是垃圾，它会导致if失败。请参阅这里的更多信息:链接

Do a

做一个

Node* revHead = NULL;

Keep in mind that maybe you may have errors like that in other part of your code as well.

请记住，在代码的其他部分也可能有类似的错误。

#3

Another method would be to first traverse the list and store all data in a stack,then create a new list and insert data in it from top of the stack.Stack being LIFO will give you the data in reverse order and hence you will have a reversed list.

另一种方法是首先遍历列表并将所有数据存储在堆栈中，然后创建一个新的列表并从堆栈顶部将数据插入其中。堆栈是LIFO会给你数据的反向顺序，因此你将有一个反向的列表。

#4

This is done using just two temporary variables.

这只使用两个临时变量。

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

Also, you can do this using recursion.

同样，您可以使用递归来实现这一点。

#5

I'm not sure, but I think you want a doubly linked list where the node has a next and previous. It will not work using an external pointer to the list. You will not have the address of the previous node.

我不确定，但我认为您需要一个双链的列表，其中节点有下一个和上一个。它不能使用指向列表的外部指针。您将没有前一个节点的地址。

If not use the method above with a stack it's a good suggestion.

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

#6

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

#7

The sample below use the recursion for reversing a linklist. I asked this Qs at a job interview. This has been tested and works. ListElem is the node.

下面的示例使用递归来反转链接列表。我在一次面试中问过这个问题。这已经经过了测试和工作。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);
    }
}

#8

The above is a reverse of 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;
}

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