從給定的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; 
    }