Создайте обратную ссылку LinkedList в C++ из данного 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 автоматически (иначе в локальной Объем тела). В C++, когда вы делаете заявление вроде этого, нет гарантии, что значение будет 0.

(если класс хранения не имеет тип static или переменная global, где он автоматически инициализируется 0, если не предусмотрено другое значение. В вашем случае переменная имеет класс памяти типа 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

Это делается с использованием только двух временных переменных.

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

выше является обратная ссылка 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 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; 
    }