Comment inverser une liste liée individuellement en utilisant seulement deux pointeurs?

109

Je me demande s'il existe une logique pour inverser une liste à lien unique en utilisant seulement deux pointeurs.

Ce qui suit est utilisé pour inverser la liste chaînée unique à l' aide de trois pointeurs à savoir p, q, r:

struct node {
    int data;
    struct node *link;
};

void reverse() {
    struct node *p = first,
                *q = NULL,
                *r;

    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    first = q;
}

Existe-t-il une autre alternative pour inverser la liste chaînée? Quelle serait la meilleure logique pour inverser une seule liste chaînée, en termes de complexité temporelle?

Madhan
la source
1
duplicata possible: stackoverflow.com/questions/818443/…
kajaco
3
Pas vraiment, c'est deux files d'attente plutôt que deux pointeurs.
paxdiablo
7
Parce que vous êtes là pour aider et que vous ne jouez pas à un jeu de répétition?
GManNickG
1
GMan: c'est le problème, je ne suis pas sûr d'aider qui que ce soit, même lui, s'il ne peut pas suivre.
1
Vous aidez ceux d'entre nous qui lisent et obtiennent quelque chose des questions et réponses. J'ai trouvé cela intéressant.
Andrew Coleson

Réponses:

133

Une alternative? Non, c'est aussi simple que possible et il n'y a pas de manière fondamentalement différente de le faire. Cet algorithme est déjà O (n) time, et vous ne pouvez pas aller plus vite que cela, car vous devez modifier chaque nœud.

Il semble que votre code soit sur la bonne voie, mais il ne fonctionne pas tout à fait sous la forme ci-dessus. Voici une version de travail:

#include <stdio.h>

typedef struct Node {
  char data;
  struct Node* next;
} Node;

void print_list(Node* root) {
  while (root) {
    printf("%c ", root->data);
    root = root->next;
  }
  printf("\n");
}

Node* reverse(Node* root) {
  Node* new_root = 0;
  while (root) {
    Node* next = root->next;
    root->next = new_root;
    new_root = root;
    root = next;
  }
  return new_root;
}

int main() {
  Node d = { 'd', 0 };
  Node c = { 'c', &d };
  Node b = { 'b', &c };
  Node a = { 'a', &b };

  Node* root = &a;
  print_list(root);
  root = reverse(root);
  print_list(root);

  return 0;
}

la source
Je ne suis pas sûr des «erreurs évidentes» dans l'original. Du point de vue du design, ne pas passer la tête de la liste et ne pas renvoyer la nouvelle tête est une mauvaise idée. Le seul bogue, cependant, est que la dernière ligne de la reverse()fonction doit être définie en premier, je crois. Sinon, le code d'origine fonctionnait correctement lorsqu'il était branché sur votre harnais de test soigné. Vous obtenez même +1 de ma part - mais une explication de ce que vous considérez comme des «erreurs évidentes» améliorerait votre réponse.
Jonathan Leffler
2
N'y a-t-il pas un bogue dans le code ci-dessus? À l'intérieur de la boucle while, vous créez à chaque fois un nouveau pointeur «suivant». Donc, s'il y a N nœuds dans la liste chaînée, vous créez N nouveaux pointeurs et vous ne les libérez ni ne les supprimez. Je pense que ce serait correct si vous créez le pointeur «suivant» avant la boucle while et faites simplement l'affectation «next = root-> next» à l'intérieur de la boucle while.
aks le
6
@aks: Il n'y a pas de fuite. Notez malloc / etc. ne sont pas appelés, il n'est donc pas nécessaire de les libérer. La variable 'next' est portée à la boucle, mais c'est parfaitement normal.
1
Même s'il n'y a pas de fuite, quel est le besoin de déclarer next à chaque fois, comme aks mentionné, "ce serait correct si vous créez le pointeur 'next' avant la boucle while et faites simplement l'affectation 'next = root-> next 'à l'intérieur de la boucle while. ", N'est-ce pas?
GeekyJ
1
J'aime vos littéraux de liste chaînée, c'est bien.
43

Je déteste être porteur de mauvaises nouvelles, mais je ne pense pas que votre solution en trois points fonctionne réellement. Lorsque je l'ai utilisé dans le faisceau de test suivant, la liste a été réduite à un nœud, selon la sortie suivante:

==========
4
3
2
1
0
==========
4
==========

Vous n'obtiendrez pas une meilleure complexité de temps que votre solution car c'est O (n) et vous devez visiter chaque nœud pour changer les pointeurs, mais vous pouvez faire une solution avec seulement deux pointeurs supplémentaires assez facilement, comme indiqué dans le code suivant:

#include <stdio.h>

// The list element type and head.

struct node { 
    int data;
    struct node *link;
};
static struct node *first = NULL;

// A reverse function which uses only two extra pointers.

void reverse() {
    // curNode traverses the list, first is reset to empty list.
    struct node *curNode = first, *nxtNode;
    first = NULL;

    // Until no more in list, insert current before first and advance.
    while (curNode != NULL) {
        // Need to save next node since we're changing the current.
        nxtNode = curNode->link;

        // Insert at start of new list.
        curNode->link = first;
        first = curNode;

        // Advance to next.
        curNode = nxtNode;
    }
}

// Code to dump the current list.

static void dumpNodes() {
    struct node *curNode = first;
    printf ("==========\n");
    while (curNode != NULL) {
        printf ("%d\n", curNode->data);
        curNode = curNode->link;
    }
}

// Test harness main program.

int main (void) {
    int i;
    struct node *newnode;

    // Create list (using actually the same insert-before-first
    // that is used in reverse function.

    for (i = 0; i < 5; i++) {
        newnode = malloc (sizeof (struct node));
        newnode->data = i;
        newnode->link = first;
        first = newnode;
    }

    // Dump list, reverse it, then dump again.

    dumpNodes();
    reverse();
    dumpNodes();
    printf ("==========\n");

    return 0;
}

Ce code génère:

==========
4
3
2
1
0
==========
0
1
2
3
4
==========

ce que je pense est ce que vous recherchiez. Il peut en fait le faire car, une fois que vous avez chargé firstle pointeur traversant la liste, vous pouvez le réutiliser firstà volonté.

paxdiablo
la source
2
Très élégant. La réutilisation du firstpointeur sur la liste chaînée elle-même permet à la solution d'utiliser seulement 2 pointeurs supplémentaires , mais 3 pointeurs au total sont toujours nécessaires pour cela.
Kevin Kibler
Vous utilisez d'abord, curNode et nxtNode, au total trois pointeurs pour cela. comment se fait-il que ce soit une solution à deux points?
Yashasvi
@Yash, relisez, deux pointeurs supplémentaires en plus first. De la même façon la solution à trois pointeur de l'OP avait first, p, qet r.
paxdiablo
@paxdiablo oh! ma faute. Désolé, j'ai mal compris la question. Merci :)
Yashasvi
25
#include <stddef.h>

typedef struct Node {
    struct Node *next;
    int data;
} Node;

Node * reverse(Node *cur) {
    Node *prev = NULL;
    while (cur) {
        Node *temp = cur;
        cur = cur->next; // advance cur
        temp->next = prev;
        prev = temp; // advance prev
    }
    return prev;
}
épisseur
la source
2
salut! Je sais que cette question est ancienne, mais pourriez-vous expliquer ce qui se passe dans cette fonction et pourquoi cela fonctionne. :) Merci!
MakeTheTrumpetsBlow
13

Voici le code pour inverser une liste liée individuellement en C .

Et ici, il est collé ci-dessous:

// reverse.c

#include <stdio.h>
#include <assert.h>

typedef struct node Node;
struct node {
    int data;
    Node *next;
};

void spec_reverse();
Node *reverse(Node *head);

int main()
{
    spec_reverse();
    return 0;
}

void print(Node *head) {
    while (head) {
        printf("[%d]->", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

void spec_reverse() {
    // Create a linked list.
    // [0]->[1]->[2]->NULL
    Node node2 = {2, NULL};
    Node node1 = {1, &node2};
    Node node0 = {0, &node1};
    Node *head = &node0;

    print(head);
    head = reverse(head);
    print(head);

    assert(head == &node2);
    assert(head->next == &node1);
    assert(head->next->next == &node0);

    printf("Passed!");
}

// Step 1:
//
// prev head  next
//   |    |    |
//   v    v    v
// NULL  [0]->[1]->[2]->NULL
//
// Step 2:
//
//      prev head  next
//        |    |    |
//        v    v    v
// NULL<-[0]  [1]->[2]->NULL
//
Node *reverse(Node *head)
{
    Node *prev = NULL;
    Node *next;

    while (head) {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }

    return prev;
}
ma11hew28
la source
4
Merci pour l'art ASCII génial d'avoir expliqué :)
achedeuzot
3

Oui. Je suis sûr que vous pouvez faire cela de la même manière que vous pouvez échanger deux numéros sans utiliser un troisième . Convertissez simplement les pointeurs en int / long et effectuez l'opération XOR plusieurs fois. C'est l'une de ces astuces C qui en fait une question amusante, mais qui n'a aucune valeur pratique.

Pouvez-vous réduire la complexité O (n)? Non, pas vraiment. Utilisez simplement une liste doublement liée si vous pensez avoir besoin de l'ordre inverse.

Brianegge
la source
… Et un nouveau problème de compatibilité 64 bits est né, si vous ne faites pas attention. Il est peu probable que vous achetiez des performances de cette façon non plus.
LnxPrgr3
2
Cela n'affectera pas la complexité du temps - c'est-à-dire que cela ne rendra pas la solution meilleure que le temps linéaire. Je veux dire, vous pourriez économiser 4 ou 8 octets de mémoire, mais cela ne changera pas la complexité globale de l'algorithme.
poundifdef
@rascher, la complexité du temps était la deuxième partie de la question. La première partie concernait la réduction du nombre de pointeurs requis.
paxdiablo
2
Je pense que l'affiche originale cherchait une astuce C bon marché. D'après mon expérience - et je l'ai profilé :) - les astuces typiques pour éviter les intermédiaires sont en fait plus lentes que d'utiliser simplement un intermédiaire.
Sera
Le lien est rompu, mais je suis sûr que l'échange de 2 numéros en utilisant XOR est de la vieille école :)
Dane
3

Robert Sedgewick, " Algorithmes en C ", Addison-Wesley, 3e édition, 1997, [Section 3.4]

Dans le cas où ce n'est pas une liste cyclique, NULL est donc le dernier lien.

typedef struct node* link;

struct node{ int item; link next; };

/* you send the existing list to reverse() and returns the reversed one */

link reverse(link x){ link t, y = x, r = NULL; while(y != NULL){ t = y->next; y-> next = r; r = y; y = t; } return r; }

limitcracker
la source
3

Juste pour le plaisir (bien que l'optimisation de la récursivité de la queue devrait l'empêcher de manger toute la pile):


Node* reverse (Node *root, Node *end) {

    Node *next = root->next;
    root->next = end;

    return (next ? reverse(next, root) : root);
}

root = reverse(root, NULL);
Andrew Johnson
la source
2
Je pense que "devrait" surestime un peu le cas. Votre compilateur C "pourrait" faire une optimisation des appels de fin, et il est assez facile de vérifier un compilateur / des options donnés, qu'il le fasse ou non: regardez le désassemblage. Ou donnez-lui quelques millions de nœuds et voyez s'il plante ;-)
Steve Jessop
3

Pour permuter deux variables sans utiliser de variable temporaire,

a = a xor b
b = a xor b
a = a xor b

le moyen le plus rapide est de l'écrire en une seule ligne

a = a ^ b ^ (b=a)

De même,

en utilisant deux swaps

swap(a,b)
swap(b,c)

solution utilisant xor

a = a^b^c
b = a^b^c
c = a^b^c
a = a^b^c

solution en une ligne

c = a ^ b ^ c ^ (a=b) ^ (b=c)
b = a ^ b ^ c ^ (c=a) ^ (a=b)
a = a ^ b ^ c ^ (b=c) ^ (c=a)

La même logique est utilisée pour inverser une liste chaînée.

typedef struct List
{
 int info;
 struct List *next;
}List;


List* reverseList(List *head)
{
 p=head;
 q=p->next;
 p->next=NULL;
 while(q)
 {
    q = (List*) ((int)p ^ (int)q ^ (int)q->next ^ (int)(q->next=p) ^ (int)(p=q));
 }
 head = p;
 return head;
}  
sr01853
la source
1
Cela suppose qu'un int a la même taille qu'un pointeur, il ne fonctionnera pas sur les systèmes amd64 (vous pouvez utiliser intptr_t). Bien qu'intéressant, échanger de cette manière n'est pas optimal sur les systèmes modernes.
ideasman42
3

Vous avez besoin d'un pointeur de piste qui suivra la liste.

Vous avez besoin de deux pointeurs:

premier pointeur pour choisir le premier nœud. deuxième pointeur pour choisir le deuxième nœud.

En traitement :

Déplacer le pointeur de piste

Pointer le deuxième nœud vers le premier nœud

Déplacer le premier pointeur d'une étape, en affectant un deuxième pointeur à un

Déplacer le deuxième pointeur d'une étape, en affectant le pointeur de piste à la deuxième

Node* reverselist( )
{
   Node *first = NULL;  // To keep first node
   Node *second = head; // To keep second node
   Node *track =  head; // Track the list

    while(track!=NULL)
    {
      track = track->next; // track point to next node;
      second->next = first; // second node point to first
      first = second; // move first node to next
      second = track; // move second node to next
    }

    track = first;

    return track;

}

Sumit Arora
la source
2

Que diriez-vous du plus lisible:


Node *pop (Node **root)
{
    Node *popped = *root;

    if (*root) {
        *root = (*root)->next;
    }

    return (popped);
}

void push (Node **root, Node *new_node)
{
    new_node->next = *root;
    *root = new_node;
}


Node *reverse (Node *root)
{
    Node *new_root = NULL;
    Node *next;

    while ((next = pop(&root))) {
        push (&new_root, next);
    }

    return (new_root);
}
Andrew Johnson
la source
2

Voici une version plus simple de Java. Il n'utilise que deux pointeurs curretprev

public void reverse(Node head) {
    Node curr = head, prev = null;

    while (head.next != null) {
        head = head.next; // move the head to next node
        curr.next = prev; //break the link to the next node and assign it to previous
        prev = curr;      // we are done with previous, move it to next node
        curr = head;      // current moves along with head
    }

    head.next = prev;     //for last node
}
Ernesto
la source
La question est de chercher une solution C, pas une à Java
Degustaf
1
La question est plus de faire l'opération inverse avec seulement deux pointeurs supplémentaires (ou références). Que ce soit C ou Java, la logique est la même.
ernesto
1

Calculez la complexité temporelle de l'algorithme que vous utilisez actuellement et il devrait être évident qu'il ne peut pas être amélioré.

John La Rooy
la source
1

Je ne comprends pas pourquoi il est nécessaire de retourner la tête alors que nous le passons comme argument. Nous passons en tête de la liste de liens, puis nous pouvons également mettre à jour. Voici une solution simple.

#include<stdio.h>
#include<conio.h>

struct NODE
{
    struct NODE *next;
    int value;
};

typedef struct NODE node;

void reverse(node **head);
void add_end(node **head,int val);
void alloc(node **p);
void print_all(node *head);

void main()
{
    node *head;
    clrscr();
    head = NULL;
    add_end( &head, 1 );
    add_end( &head, 2 );
    add_end( &head, 3 );
    print_all( head );
    reverse( &head );
    print_all( head );
    getch();
}
void alloc(node **p)
{
    node *temp;
    temp = (node *) malloc( sizeof(node *) );
    temp->next = NULL;
    *p = temp;
}
void add_end(node **head,int val)
{
    node *temp,*new_node;
    alloc(&new_node);
    new_node->value = val;
    if( *head == NULL )
    {
        *head = new_node;
        return;
    }
    for(temp = *head;temp->next!=NULL;temp=temp->next);
    temp->next = new_node;
}
void print_all(node *head)
{
    node *temp;
    int index=0;
    printf ("\n\n");
    if (head == NULL)
    {
        printf (" List is Empty \n");
        return;
    }
    for (temp=head; temp != NULL; temp=temp->next,index++)
        printf (" %d ==> %d \n",index,temp->value);
}
void reverse(node **head)
{
    node *next,*new_head;
    new_head=NULL;
    while(*head != NULL)
    {
        next = (*head)->next;
        (*head)->next = new_head;
        new_head = (*head);
        (*head) = next;
    }
    (*head)=new_head;
}
Hardik Chauhan
la source
1
#include <stdio.h>
#include <malloc.h>

tydef struct node
{
    int info;
    struct node *link;
} *start;

void main()
{
    rev();
}

void rev()
{
    struct node *p = start, *q = NULL, *r;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }

    start = q;
}
Shridhar Gadade
la source
0

Non, rien de plus rapide que le courant O (n) ne peut être fait. Vous devez modifier chaque nœud, donc le temps sera de toute façon proportionnel au nombre d'éléments et c'est O (n) que vous avez déjà.

dents acérées
la source
0

L'utilisation de deux pointeurs tout en maintenant la complexité temporelle de O (n), le plus rapide possible, ne peut être possible que par la conversion de nombre de pointeurs et l'échange de leurs valeurs. Voici une implémentation:

#include <stdio.h>

typedef struct node
{
    int num;
    struct node* next;
}node;

void reverse(node* head)
{
   node* ptr;
   if(!head || !head->next || !head->next->next) return;
   ptr = head->next->next;
   head->next->next = NULL;
   while(ptr)
   {
     /* Swap head->next and ptr. */
     head->next = (unsigned)(ptr =\
     (unsigned)ptr ^ (unsigned)(head->next =\
     (unsigned)head->next ^ (unsigned)ptr)) ^ (unsigned)head->next;

     /* Swap head->next->next and ptr. */
     head->next->next = (unsigned)(ptr =\
     (unsigned)ptr ^ (unsigned)(head->next->next =\
     (unsigned)head->next->next ^ (unsigned)ptr)) ^ (unsigned)head->next->next;
   }
}

void add_end(node* ptr, int n)
{
    while(ptr->next) ptr = ptr->next;
    ptr->next = malloc(sizeof(node));
    ptr->next->num = n;
    ptr->next->next = NULL;
}

void print(node* ptr)
{
    while(ptr = ptr->next) printf("%d ", ptr->num);
    putchar('\n');
}

void erase(node* ptr)
{
    node *end;
    while(ptr->next)
    {
        if(ptr->next->next) ptr = ptr->next;
        else
        {
            end = ptr->next;
            ptr->next = NULL;
            free(end);
        }
    }
}

void main()
{
    int i, n = 5;
    node* dummy_head;
    dummy_head->next = NULL;
    for(i = 1; i <= n ; ++i) add_end(dummy_head, i);
    print(dummy_head);
    reverse(dummy_head);
    print(dummy_head);
    erase(dummy_head);
}
Apshir
la source
0

J'ai une approche légèrement différente. Je voulais utiliser les fonctions existantes (comme insert_at (index), delete_from (index)) pour inverser la liste (quelque chose comme une opération de décalage à droite). La complexité est toujours O (n) mais l'avantage est un code plus réutilisé. Jetez un œil à la méthode another_reverse () et dites-moi ce que vous en pensez tous.

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

struct node {
    int data;
    struct node* next;
};

struct node* head = NULL;

void printList(char* msg) {
    struct node* current = head;

    printf("\n%s\n", msg);

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
}

void insert_beginning(int data) {
    struct node* newNode = (struct node*) malloc(sizeof(struct node));

    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL)
    {
        head = newNode;
    } else {
        newNode->next = head;
        head = newNode;
    }
}

void insert_at(int data, int location) {

    struct node* newNode = (struct node*) malloc(sizeof(struct node));

    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL)
    {
        head = newNode;
    }

    else {
        struct node* currentNode = head;
        int index = 0;

        while (currentNode != NULL && index < (location - 1)) {
            currentNode = currentNode->next;
            index++;
        }

        if (currentNode != NULL)
        {
            if (location == 0) {
                newNode->next = currentNode;
                head = newNode;
            } else {
                newNode->next = currentNode->next;
                currentNode->next = newNode;
            }
        }
    }
}


int delete_from(int location) {

    int retValue = -1;

    if (location < 0 || head == NULL)
    {
        printf("\nList is empty or invalid index");
        return -1;
    } else {

        struct node* currentNode = head;
        int index = 0;

        while (currentNode != NULL && index < (location - 1)) {
            currentNode = currentNode->next;
            index++;
        }

        if (currentNode != NULL)
        {
            // we've reached the node just one prior to the one we want to delete

            if (location == 0) {

                if (currentNode->next == NULL)
                {
                    // this is the only node in the list
                    retValue = currentNode->data;
                    free(currentNode);
                    head = NULL;
                } else {

                    // the next node should take its place
                    struct node* nextNode = currentNode->next;
                    head = nextNode;
                    retValue = currentNode->data;
                    free(currentNode);
                }
            } // if (location == 0)
            else {
                // the next node should take its place
                struct node* nextNode = currentNode->next;
                currentNode->next = nextNode->next;

                if (nextNode != NULL
                ) {
                    retValue = nextNode->data;
                    free(nextNode);
                }
            }

        } else {
            printf("\nInvalid index");
            return -1;
        }
    }

    return retValue;
}

void another_reverse() {
    if (head == NULL)
    {
        printf("\nList is empty\n");
        return;
    } else {
        // get the tail pointer

        struct node* tailNode = head;
        int index = 0, counter = 0;

        while (tailNode->next != NULL) {
            tailNode = tailNode->next;
            index++;
        }

        // now tailNode points to the last node
        while (counter != index) {
            int data = delete_from(index);
            insert_at(data, counter);
            counter++;
        }
    }
}

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

    insert_beginning(4);
    insert_beginning(3);
    insert_beginning(2);
    insert_beginning(1);
    insert_beginning(0);

    /*  insert_at(5, 0);
     insert_at(4, 1);
     insert_at(3, 2);
     insert_at(1, 1);*/

    printList("Original List\0");

    //reverse_list();
    another_reverse();

    printList("Reversed List\0");

    /*  delete_from(2);
     delete_from(2);*/

    //printList();
    return 0;
}
FunBoy
la source
0
using 2-pointers....bit large but simple and efficient

void reverse()

{

int n=0;

node *temp,*temp1;

temp=strptr;

while(temp->next!=NULL)

{

n++;      //counting no. of nodes

temp=temp->next;

}
// we will exchange ist by last.....2nd by 2nd last so.on....
int i=n/2;  

temp=strptr;

for(int j=1;j<=(n-i+1);j++)

temp=temp->next;
//  i started exchanging from in between ....so we do no have to traverse list so far //again and again for exchanging

while(i>0)

{

temp1=strptr;

for(int j=1;j<=i;j++)//this loop for traversing nodes before n/2

temp1=temp1->next;

int t;

t=temp1->info;

temp1->info=temp->info;

temp->info=t;

i--;

temp=temp->next; 

//at the end after exchanging say 2 and 4 in a 5 node list....temp will be at 5 and we will traverse temp1 to ist node and exchange ....

}

}
Amit Puri
la source
0
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *first=NULL,*last=NULL,*next,*pre,*cur,*temp;
void create()
{
cur=(struct node*) malloc(sizeof(struct node));
printf("enter first data to insert");
scanf("%d",&cur->data);
first=last=cur;
first->link=NULL;
}
void insert()
{
int pos,c;
cur=(struct node*) malloc(sizeof(struct node));
printf("enter data to insert and also its position");
scanf("%d%d",&cur->data,&pos);
if(pos==1)
{
cur->link=first;
first=cur;
}
else
{
c=1;
    next=first;
    while(c<pos)
    {
        pre=next;
        next=next->link;
        c++;
    }
        if(pre==NULL)
        {
            printf("Invalid position");
        }
        else
        {
        cur->link=pre->link;
        pre->link=cur;
        }
}
}
void display()
{
cur=first;
while(cur!=NULL)
{
printf("data= %d\t address= %u\n",cur->data,cur);
cur=cur->link;
}
printf("\n");
}
void rev()
{
pre=NULL;
cur=first;
while(cur!=NULL)
{
next=cur->link;
cur->link=pre;
pre=cur;
cur=next;
}
first=pre;
}
void main()
{
int choice;
clrscr();
do
{
printf("Options are: -\n1:Create\n2:Insert\n3:Display\n4:Reverse\n0:Exit\n");
printf("Enter your choice: - ");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
insert();
break;
case 3:
display();
break;
case 4:
rev();
break;
case 0:
exit(0);
default:
printf("wrong choice");
}
}
while(1);
}
M. Amit Kumar
la source
Contactez-moi pour tout problème d'implémentation C.
M. Amit Kumar le
0

Oui, il existe un moyen d'utiliser seulement deux pointeurs. C'est en créant une nouvelle liste chaînée où le premier nœud est le premier nœud de la liste donnée et le second nœud de la première liste est ajouté au début de la nouvelle liste et ainsi de suite.

deepak verma
la source
0

Voici ma version:

void reverse(ListElem *&head)
{
    ListElem* temp;
    ListElem* elem = head->next();
    ListElem* prev = head;
    head->next(0);

    while(temp = elem->next())
    {
        elem->next(prev);
        prev = elem;
        elem = temp;
    }
    elem->next(prev);
    head = elem;
}

class ListElem{
public:
    ListElem(int val): _val(val){}
    ListElem *next() const { return _next; }
    void next(ListElem *elem) { _next = elem; }
    void val(int val){ _val = val; }
    int val() const { return _val;}
private:
    ListElem *_next;
    int _val;
};
cpp
la source
0

J'utilise java pour implémenter cela et l'approche est un développement piloté par les tests, donc des cas de test sont également joints.

La classe Node qui représente un nœud unique -

package com.adnan.linkedlist;

/**
 * User  : Adnan
 * Email : [email protected]
 * Date  : 9/21/13
 * Time  : 12:02 PM
 */
public class Node {

    public Node(int value, Node node){
        this.value = value;
        this.node = node;
    }
    private int value;
    private Node node;

    public int getValue() {
        return value;
    }

    public Node getNode() {
        return node;
    }

    public void setNode(Node node){
        this.node = node;
    }
}

Classe de service qui prend le nœud de démarrage comme entrée et le réserve sans utiliser d'espace supplémentaire.

package com.adnan.linkedlist;

/**
 * User  : Adnan
 * Email : [email protected]
 * Date  : 9/21/13
 * Time  : 11:54 AM
 */
public class SinglyLinkedListReversal {

    private static final SinglyLinkedListReversal service 
= new SinglyLinkedListReversal();
    public static SinglyLinkedListReversal getService(){
        return service;
    }



    public Node reverse(Node start){
        if (hasOnlyNodeInLinkedList(start)){
            return start;
        }
        Node firstNode, secondNode, thirdNode;
        firstNode = start;
        secondNode = firstNode.getNode();
        while (secondNode != null ){
            thirdNode = secondNode.getNode();
            secondNode.setNode(firstNode);
            firstNode = secondNode;
            secondNode = thirdNode;
        }
        start.setNode(null);
        return firstNode;
    }

    private boolean hasOnlyNodeInLinkedList(Node start) {
        return start.getNode() == null;
    }


}

Et le cas de test qui couvre le scénario ci-dessus. Veuillez noter que vous avez besoin de pots junit. J'utilise testng.jar; vous pouvez utiliser tout ce qui vous plaît.

package com.adnan.linkedlist;

import org.testng.annotations.Test;

import static org.testng.AssertJUnit.assertTrue;

/**
 * User  : Adnan
 * Email : [email protected]
 * Date  : 9/21/13
 * Time  : 12:11 PM
 */
public class SinglyLinkedListReversalTest {

    private SinglyLinkedListReversal reversalService = 
SinglyLinkedListReversal.getService();

    @Test
    public void test_reverseSingleElement() throws Exception {
        Node node = new Node(1, null);
        reversalService.reverse(node);
        assertTrue(node.getNode() == null);
        assertTrue(node.getValue() == 1);
    }


    //original - Node1(1) -> Node2(2) -> Node3(3)
    //reverse - Node3(3) -> Node2(2) -> Node1(1)
    @Test
    public void test_reverseThreeElement() throws Exception {
        Node node3 = new Node(3, null);
        Node node2 = new Node(2, node3);
        Node start = new Node(1, node2);


        start = reversalService.reverse(start);
        Node test = start;
        for (int i = 3; i >=1 ; i -- ){
          assertTrue(test.getValue() == i);
            test = test.getNode();
        }


    }

    @Test
    public void test_reverseFourElement() throws Exception {
        Node node4 = new Node(4, null);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node start = new Node(1, node2);


        start = reversalService.reverse(start);
        Node test = start;
        for (int i = 4; i >=1 ; i -- ){
            assertTrue(test.getValue() == i);
            test = test.getNode();
        }
    }

        @Test
        public void test_reverse10Element() throws Exception {
            Node node10 = new Node(10, null);
            Node node9 = new Node(9, node10);
            Node node8 = new Node(8, node9);
            Node node7 = new Node(7, node8);
            Node node6 = new Node(6, node7);
            Node node5 = new Node(5, node6);
            Node node4 = new Node(4, node5);
            Node node3 = new Node(3, node4);
            Node node2 = new Node(2, node3);
            Node start = new Node(1, node2);


            start = reversalService.reverse(start);
            Node test = start;
            for (int i = 10; i >=1 ; i -- ){
                assertTrue(test.getValue() == i);
                test = test.getNode();
            }


    }

    @Test
    public void test_reverseTwoElement() throws Exception {
        Node node2 = new Node(2, null);
        Node start = new Node(1, node2);


        start = reversalService.reverse(start);
        Node test = start;
        for (int i = 2; i >=1 ; i -- ){
            assertTrue(test.getValue() == i);
            test = test.getNode();
        }


    }
}
Mohammad Adnan
la source
0

Un algorithme simple si vous utilisez la liste chaînée comme structure de pile:

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

typedef struct list {
    int key;
    char value;
    struct list* next;
} list;
void print(list*);
void add(list**, int, char);
void reverse(list**);
void deleteList(list*);

int main(void) {
    list* head = NULL;
    int i=0;
    while ( i++ < 26 ) add(&head, i, i+'a');
    printf("Before reverse: \n");
    print(head);
    printf("After reverse: \n");
    reverse(&head);
    print(head);
    deleteList(head);

}
void deleteList(list* l) {

    list* t = l;    
    while ( t != NULL ) {
        list* tmp = t;
        t = t->next;
        free(tmp);
    }

}
void print(list* l) {
    list* t = l;
    while ( t != NULL) {
        printf("%d:%c\n", t->key, t->value);
        t = t->next;
    }
}

void reverse(list** head) {
    list* tmp = *head;
    list* reversed = NULL;
    while ( tmp != NULL ) {
        add(&reversed, tmp->key, tmp->value);
        tmp = tmp->next;
    }
    deleteList(*head);
    *head = reversed;
}

void add(list** head, int k, char v) {

    list* t = calloc(1, sizeof(list));
    t->key = k; t->value = v;
    t->next = *head;
    *head = t;

}

Les performances peuvent être affectées depuis l'appel de fonction supplémentaire à l'ajout et à malloc, de sorte que les algorithmes d'échange d'adresses sont meilleurs mais que l'on crée en fait une nouvelle liste afin que vous puissiez utiliser des options supplémentaires comme trier ou supprimer des éléments si vous ajoutez une fonction de rappel en tant que paramètre au inverser.

Ilian Zapryanov
la source
0

Voici une approche légèrement différente, mais simple en C ++ 11:

#include <iostream>

struct Node{
    Node(): next(NULL){}
    Node *next;
    std::string data;
};

void printlist(Node* l){
    while(l){
        std::cout<<l->data<<std::endl;
        l = l->next;
    }
    std::cout<<"----"<<std::endl;
}

void reverse(Node*& l)
{
    Node* prev = NULL;
    while(l){
        auto next = l->next;
        l->next = prev;
        prev=l;
        l=next;
    }
    l = prev;
}

int main() {
    Node s,t,u,v;
    s.data = "1";
    t.data = "2";
    u.data = "3";
    v.data = "4";
    s.next = &t;
    t.next = &u;
    u.next = &v;
    Node* ptr = &s;
    printlist(ptr);
    reverse(ptr);
    printlist(ptr);
    return 0;
}

Sortie ici

Carl
la source
0

Voici une implémentation utilisant 2 pointeurs (head et r)

ListNode * reverse(ListNode* head) {

    ListNode *r = NULL;

    if(head) {
        r = head->next;
        head->next = NULL;
    }

    while(r) {
        head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r->next));
        r->next = reinterpret_cast<ListNode*>(size_t(r->next) ^ size_t(head));
        head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r->next));

        head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r));
        r = reinterpret_cast<ListNode*>(size_t(r) ^ size_t(head));
        head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r));
    }
    return head;
}
ARC
la source
Aussi intelligent et indéchiffrable que cela puisse être, vous avez des problèmes si sizeof(size_t) < sizeof(ListNode*)... vous devez utiliser std::uintptr_t.
Quentin
0

voici une petite solution simple ...

void reverse()
{
    node * pointer1 = head->next;
    if(pointer1 != NULL)
    {
        node *pointer2 = pointer1->next;
        pointer1->next = head;
        head->next = NULL;
        head = pointer1;

        if(pointer2 != NULL)
        {

            while(pointer2 != NULL)
            {
                pointer1 = pointer2;
                pointer2 = pointer2->next;
                pointer1->next = head;
                head = pointer1;
            }

            pointer1->next = head;
            head = pointer1;
        }       
   }
 }
waqar ahmed
la source
0

Vous pouvez résoudre ce problème à l'aide d'un seul pointeur supplémentaire, qui doit être statique pour la fonction inverse. C'est en complexité O (n).

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

typedef struct List* List;
struct List {
   int val;
   List next;
};

List reverse(List list) { /* with recursion and one static variable*/
    static List tail;
    if(!list || !list->next) {
        tail = list;

        return tail;
    } else {
        reverse1(list->next);
        list->next->next = list;
        list->next = NULL;

        return tail;
    }
}
Shailendra Shrivastav
la source
0

Comme alternative, vous pouvez utiliser la récursivité-

struct node* reverseList(struct node *head)
{
    if(head == NULL) return NULL;
    if(head->next == NULL) return head;

    struct node* second = head->next;       
    head->next = NULL;

    struct node* remaining = reverseList(second);
    second->next = head;

    return remaining;
}
vaibhav
la source
Comment est-ce correct. Vous utilisez plus de deux pointeurs, il est simplement caché sur la pile chaque fois que vous effectuez un appel de fonction.
Mike G
0
curr = head;
prev = NULL;

while (curr != NULL) {
    next = curr->next; // store current's next, since it will be overwritten
    curr->next = prev;
    prev = curr;
    curr = next;
}

head = prev; // update head
Jostein Topland
la source
0
class Node {
    Node next;
    int data;

    Node(int item) {
        data = item;
        next = null;
    }
}

public class LinkedList {

    static Node head;

    //Print LinkedList
    public static void printList(Node node){

        while(node!=null){
            System.out.print(node.data+" ");
            node = node.next;
        }
        System.out.println();
    }

    //Reverse the LinkedList Utility
    public static Node reverse(Node node){

        Node new_node = null;

        while(node!=null){

            Node next = node.next;
            node.next = new_node;
            new_node = node;
            node = next;

        }
        return new_node;
    }

    public static void main(String[] args) {

        //Creating LinkedList
        LinkedList.head = new Node(1);
        LinkedList.head.next = new Node(2);
        LinkedList.head.next.next = new Node(3);
        LinkedList.head.next.next.next = new Node(4);

        LinkedList.printList(LinkedList.head);

        Node node = LinkedList.reverse(LinkedList.head);

        LinkedList.printList(node);

    }


}
Raju Muke
la source
node n'est pas un pointeur, nous venons de passer head comme node. Faites-moi savoir si vous avez besoin de plus de précisions
Raju Muke