Создать обратный 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 терпит неудачу. Подробнее см. Здесь: Ссылка

Do

Node* revHead = NULL;

Имейте в виду, что, возможно, у вас могут быть подобные ошибки и в другой части вашего кода.

Answer 3

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

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 4

Другим методом будет сначала просмотреть список и сохранить все данные в стеке, а затем создать новый список и вставить в него данные из верхней части стека. Если использовать LIFO, то данные будут в обратном порядке, и, следовательно, вы будет иметь обратный список.

Answer 5

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

Answer 6

В приведенном ниже примере используется рекурсия для обращения к списку ссылок. Я задал этот вопрос на собеседовании. Это было проверено и работает. 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 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

Я не уверен, но я думаю, что вам нужен двусвязный список, в котором у узла есть следующий и предыдущий.Он не будет работать с использованием внешнего указателя на список.У вас не будет адреса предыдущего узла.

Если вы не используете описанный выше метод со стеком, это хорошее предложение.

Answer 9

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