Поменять местами указатели в связанном списке

Question

Здравствуйте, ребята, не могли бы вы помочь мне в написании процедуры для изменения указателей в связанном списке. например, A-> B-> C-> D станет A <-B <-C <-D без использования дополнительного связанного списка. </p>

Edit: ------ хорошо, ребята, так что я искал решение этой проблемы, вот код на случай, если вы захотите:

    void reverse_list(){
    struct node *next, *current,*previous;
    previous = NULL; 
    current =head; 
    while(current != NULL){
    next = current->next; 
    current->next = previous; 
    previous=current; 
    current = next; 
    }
    head = previous; 
    }

Answer 1

Поскольку вы не упомянули, реализуете ли вы связанный список самостоятельно или нет.

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

#include<stdio.h>
#include<stdlib.h>//for using malloc

struct Node//Defining a structure for linked list's node
{
    int info;//assuming it is an integer linked list
    struct Node *link;//this pointer links a node to it's immediate neighbor node
};

struct Node *head=NULL,*temp;//some initializations and declarations

void insertion(int data)//To insert elements to linked list
{
    struct Node *ptr;
    ptr=malloc(sizeof(*ptr));//creating a new node for the newcomer
    ptr->info=data;//taking the given integer value for the node to hold

    //initializing with null as the current node may be the last node and
    //if it is then it will point nobody
    //...but if it is not when a new node comes in the future it will eventually be
    //replaced to point the newcomer
    ptr->link=NULL;

    if(head==NULL)//head still null means we are creating the first node
    {             //handling the head separately as it has no parent node
        head=ptr;
        temp=ptr;//copying the current node's pointer to temp such that we can
        //find it as a parent of next node
    }
    else//for the rest of the nodes' creation
    {
        //as temp is the pointer to the previous node, so previous node is linking
        //to its next node, i.e, the current node
        temp->link=ptr;

        //updating the temp to point the current node such that it can act as a parent node
        //when the next node comes
        temp=ptr;
    }
}

void reversePointers()
{
    struct Node *trav,*from=NULL,*temp;
    for(trav=head;;)
    {
        if(trav->link==NULL)//if we have reached to the end
        {
            head=trav;//then the reverse linked list's head should point to the last element
            trav->link=from;//and making the second last node as it's next node
            break;
        }
        temp=trav;//saving current node pointer to update the "from" pointer
        trav=trav->link;//advancing current node pointer to forward
        temp->link=from;//making the current node to point to it's previous node
        from=temp;//saving current node's pointer which will be used in next iteration
    }
}

void traverse()//to traverse the nodes
{
    struct Node *ptr=head;
    while(ptr!=NULL)
    {
        printf("%d ",ptr->info);
        ptr=ptr->link;
    }
    printf("\n");
}

int main(void)
{
    int i,n,t;

    printf("Enter Number of elements: ");
    scanf("%d",&n);

    printf("Enter Elements: ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&t);
        insertion(t);
    }
    printf("Before reversing the pointers the elements are: ");
    traverse();

    //let's reverse the pointers to make the list to go backward
    reversePointers();

    printf("After reversing the pointers the elements are: ");
    traverse();

}

Во-вторых, если вы используете список STL, то подход довольно прост.Просто используйте,

your_list_name.reverse()

Опять же, если вы хотите перевернуть список STL только для целей итерации, тогда нет необходимости фактически переворачивать его.Вместо этого вы можете использовать обратный итератор следующим образом (скажем, для целочисленного списка):

for(list<int>::reverse_iterator it=your_list_name.rbegin();it!=your_list_name.rend();it++)
{
    //do whatever you want
}

Answer 2

Вы можете думать о списке как о стеке. Тогда вы могли бы легко перевернуть такой список, «вытолкнув» узлы и «вытолкнув» их в новый список.

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