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

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类是在当地的自动（又名范围体）。在C++当你做这样的声明时，不能保证该值将是0。

（除非存储类是static类型或变量是global其中如果设置为任何其他值将被自动初始化为0。在你的情况中的变量存储类auto类型，这意味着它是在本地定义的一个函数，当声明一个局部变量时，没有指定一个值，这个值是垃圾。请记住，使用下一个C++标准C++0x关键字auto有一个新的含义）。

你的情况的值是垃圾，使if失败。这里查看更多信息：Link

做一个

Node* revHead = NULL; 

请记住，也许你可能有这样的在你的代码的其他部分的错误也是如此。

Answer 3

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

Answer 4

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 5

这只用两个临时变量就可以完成。

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 6

我不确定，但我想你想要一个双向链接列表，其中节点具有next和previous。它不会使用外部指针指向列表。您将不会拥有前一个节点的地址。

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

Answer 7

以上是链接列表

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 8

反向下面示例使用递归逆转链表。我在面试时问了这个问题。这已经过测试和工作。 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 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; 
    }