Как двигаться назад в связанном списке?

Допустим, у меня есть строка «Лампы», она передается в мою программу, и каждый символ сохраняется в узле в связанном списке.

Мне нужно скопировать этот список в обратном порядке, используя другой связанный список, как мне это сделать, я продвинулся довольно далеко, но как мне двигаться назад в связанном списке?

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

#include <stdlib.h>
#include <stdio.h>

struct NODE {
    struct NODE *next;  
    char data;

};


int main(int argc, char *argv[]) {

int i;

struct NODE *head;
struct NODE *current;
struct NODE *head2;
struct NODE *current2;
struct NODE *finger;


for(i = 0; i < argc; i++)
    printf("arg %d: %s\n", i, argv[i]);

head = (struct NODE*)malloc(sizeof(struct NODE));
    current = head;


    for ( i = 0; i < sizeof(argv[1]) - 1; i++ ) {

    current -> data = argv[1][i];
    current -> next = (struct node*)malloc(sizeof(struct NODE));
    current = current -> next;
    current -> next = NULL;

}


head2 = (struct NODE*)malloc(sizeof(struct NODE));
    current2 = head2;

    while ( current != head) {

        finger = head;


    while (finger -> next != current) 

        finger = finger -> next;
        current2 -> data = current -> data;
        current2 -> next = (struct node*)malloc(sizeof(struct NODE));
        current2 = current2 -> next;    
        // move backwards



    } // ends loop



}






return 0;

}

c linked-list reverse
person Anthony Paliseno    schedule 28.02.2013    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Как двигаться назад в (односвязном) списке?

Вы не знаете. Хитрость преобразования одного списка в другой заключается в вставке в начало, а не в конец целевого списка. Вам нужно пройти по исходному списку обычным способом, следуя указателям next, но вместо того, чтобы добавлять элементы в конец целевого списка, создайте новый узел и замените им заголовок цели.

Вот пошаговая иллюстрация:

sourceHead -> "A" -> "B" -> "C" -> NULL
your pointer   ^
targetHead -> NULL

sourceHead -> "A" -> "B" -> "C" -> NULL
your pointer          ^
targetHead -> "A" -> NULL

sourceHead -> "A" -> "B" -> "C" -> NULL
your pointer                 ^
targetHead -> "B" -> "A" -> NULL

sourceHead -> "A" -> "B" -> "C" -> NULL
your pointer                        ^
targetHead -> "C" -> "B" -> "A" -> NULL
person Sergey Kalinichenko    schedule 28.02.2013

arrow_upward
2
arrow_downward

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

person silentcoder    schedule 28.02.2013