Come invertire una lista collegata singolarmente usando solo due puntatori?

Mi chiedo se esiste qualche logica per invertire la lista collegata usando solo due puntatori.

Quanto segue è usato per invertire la singola lista collegata usando tre puntatori vale a dire 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; } q = first; } 

C’è un altro sostituto per invertire la lista concatenata? quale sarebbe la migliore logica per invertire una lista concatenata, in termini di complessità temporale?

Qualche alternativa? No, questo è semplice come si ottiene, e non c’è un modo fondamentalmente diverso di farlo. Questo algoritmo è già O (n), e non è ansible ottenere più velocemente di così, poiché è necessario modificare ogni nodo.

Sembra che il tuo codice sia sulla strada giusta, ma non funziona abbastanza nel modulo in alto. Ecco una versione funzionante:

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

Detesto essere il portatore di cattive notizie, ma non credo che la tua soluzione a tre puntini funzioni effettivamente. Quando l’ho usato nel seguente cablaggio di test, l’elenco è stato ridotto a un nodo, come da seguente output:

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

Non avrai una complessità temporale migliore della tua soluzione dato che è O (n) e devi visitare ogni nodo per cambiare i puntatori, ma puoi fare una soluzione con solo due puntatori extra abbastanza facilmente, come mostrato nel seguente codice:

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

Questo codice emette:

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

che penso sia ciò che cercavi. Può effettivamente farlo poiché, una volta caricati per first nel puntatore che attraversa l’elenco, puoi riutilizzarlo per first a piacimento.

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

Ecco il codice per invertire un elenco collegato singolarmente in C.

E qui è incollato di seguito:

 // reverse.c #include  #include  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 // | | | // vvv // NULL [0]->[1]->[2]->NULL // // Step 2: // // prev head next // | | | // vvv // 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; } 

Sì. Sono sicuro che puoi farlo nello stesso modo in cui puoi scambiare due numeri senza usare un terzo . Basta lanciare i puntatori a un int / long ed eseguire l’operazione XOR un paio di volte. Questo è uno di quei trucchetti che rende una domanda divertente, ma non ha alcun valore pratico.

Puoi ridurre la complessità di O (n)? No, non proprio. Usa una lista doppiamente collegata se pensi di aver bisogno di un ordine inverso.

Robert Sedgewick, ” Algorithms in C “, Addison-Wesley, 3rd Edition, 1997, [Sezione 3.4]

Nel caso in cui non sia una lista ciclica, quindi NULL è l’ultimo link.

 typedef struct node* link; 

typedef struct node* link;

nodo struct {
object int;
link successivo;
};

/ * si invia la lista esistente per invertire () e restituisce quella invertita * /

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

Solo per divertimento (anche se l’ottimizzazione della ricorsione in coda dovrebbe smettere di mangiare tutto lo stack):

 Node* reverse (Node *root, Node *end) { Node *next = root->next; root->next = end; return (next ? reverse(next, root) : root); } root = reverse(root, NULL); 

Per scambiare due variabili senza l’uso di una variabile temporanea,

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

il modo più veloce è scriverlo in una riga

 a = a ^ b ^ (b=a) 

Allo stesso modo,

usando due swap

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

soluzione usando xor

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

soluzione in una riga

 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 stessa logica viene utilizzata per invertire una lista collegata.

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

Hai bisogno di un puntatore traccia che seguirà l’elenco.

Hai bisogno di due indicatori:

primo puntatore a scegliere il primo nodo. secondo puntatore per selezionare il secondo nodo.

In lavorazione :

Sposta puntatore traccia

Punto secondo nodo al primo nodo

Sposta il primo puntatore di un passo, assegnando il secondo puntatore a uno

Sposta il secondo puntatore di un passo, assegnando il puntatore traccia al secondo

 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; 

}

Che ne dici del più leggibile:

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

Ecco una versione più semplice in Java. Usa solo due puntatori curr e prev

 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 } 

Non capisco perché ci sia bisogno di tornare a capo mentre lo passiamo come argomento. Stiamo passando alla testa della lista dei link, quindi possiamo anche aggiornare. Di seguito è semplice soluzione.

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

Calcola la complessità temporale dell’algoritmo che stai utilizzando ora e dovrebbe essere ovvio che non può essere migliorato.

No, non può essere fatto nulla più veloce dell’attuale O (n). Devi modificare ogni nodo, quindi il tempo sarà proporzionale al numero di elementi comunque e questo è O (n) che hai già.

L’utilizzo di due puntatori, pur mantenendo la complessità temporale di O (n), il più veloce ottenibile, potrebbe essere ansible solo attraverso il lancio di numeri di puntatori e lo scambio dei loro valori. Ecco una implementazione:

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

Ho un approccio leggermente diverso. Volevo sfruttare le funzioni esistenti (come insert_at (index), delete_from (index)) per invertire la lista (qualcosa come un’operazione di spostamento a destra). La complessità è ancora O (n), ma il vantaggio è il codice più riutilizzato. Dai un’occhiata al metodo another_reverse () e fammi sapere cosa ne pensi.

 #include  #include  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; } 
 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 .... } } 
 #include #include #include 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(clink; 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); } 

Sì, c’è un modo usando solo due puntatori. Cioè creando una nuova lista collegata dove il primo nodo è il primo nodo della lista data e il secondo nodo della prima lista viene aggiunto all’inizio del nuovo elenco e così via.

Ecco la mia versione:

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

dove

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

Sto usando java per implementarlo e l’approccio è uno sviluppo basato su test, quindi anche i test case sono allegati.

La class Node che rappresenta un singolo nodo –

 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 di servizio che prende come input il nodo iniziale e lo riserva senza utilizzare spazio aggiuntivo.

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

E il test case che copre lo scenario sopra. Si prega di notare che avete bisogno di junit jars. Sto usando testng.jar; puoi usare qualsiasi cosa ti piaccia ..

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

Un algoritmo semplice se si utilizza l’elenco collegato come struttura dello stack:

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

Le prestazioni potrebbero essere influenzate dal richiamo della funzione addizionale all’add e al malloc in modo che gli algoritmi degli swap degli indirizzi siano migliori ma che in realtà crei un nuovo elenco in modo da poter utilizzare opzioni aggiuntive come ordinare o rimuovere elementi se si aggiunge una funzione di callback come parametro al inverso.

Ecco un approccio leggermente diverso, ma semplice in C ++ 11:

 #include  struct Node{ Node(): next(NULL){} Node *next; std::string data; }; void printlist(Node* l){ while(l){ std::cout<data<next; } std::cout<<"----"<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; } 

Uscita qui

Di seguito è una implementazione utilizzando 2 puntatori (testa e r)

 ListNode * reverse(ListNode* head) { ListNode *r = NULL; if(head) { r = head->next; head->next = NULL; } while(r) { head = reinterpret_cast(size_t(head) ^ size_t(r->next)); r->next = reinterpret_cast(size_t(r->next) ^ size_t(head)); head = reinterpret_cast(size_t(head) ^ size_t(r->next)); head = reinterpret_cast(size_t(head) ^ size_t(r)); r = reinterpret_cast(size_t(r) ^ size_t(head)); head = reinterpret_cast(size_t(head) ^ size_t(r)); } return head; } 

ecco una soluzione un po ‘semplice …

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

È ansible risolvere questo problema con l’aiuto di un solo puntatore aggiuntivo, che deve essere statico per la funzione inversa. È in O (n) complessità.

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

In alternativa, puoi usare la ricorsione-

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

Soluzione utilizzando 1 variabile (solo p ):

 typedef unsigned long AddressType; #define A (*( AddressType* )&p ) #define B (*( AddressType* )&first->link->link ) #define C (*( AddressType* )&first->link ) /* Reversing linked list */ p = first; while( first->link ) { A = A + B + C; B = A - B - C; A = A - B; C = A - C; A = A - C; } first = p;