特定の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

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であるか、または変数が他の値が提供されていない場合、それは自動的に0に初期化されglobalでなければ（あなたのケースでは、変数は、それがローカルに定義されている意味するタイプautoのストレージクラスを有します次のC++標準C++0xではキーワードautoに新しい意味があることに注意してください）。

あなたのケースの値は、ifが失敗するゴミです。ここではより多くの情報を参照してください：Link

多分あなたは同様にあなたのコードの他の部分でそのような誤差がある場合がございますことを心に留めて

Node* revHead = NULL; 

してくださいください。

Answer 3

もう一つの方法は、最初のリストと店を横断するだろうスタック内のすべてのデータを作成し、新しいリストを作成し、スタックの上からデータを挿入します.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

これは、ただ2つの一時変数を使用して行われます。

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

私は確信していませんが、ノードに次と前のノードがある二重リンクリストが必要です。リストへの外部ポインタを使用しても機能しません。前のノードのアドレスは持っていません。

上記の方法をスタックで使用しない場合は、良い提案です。

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

以下のサンプルは、LINKLISTを反転させるために再帰を使用しています。私は仕事の面接でこの質問をしました。これはテストされ、動作しています。 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; 
    }