Como reverter uma lista vinculada individualmente usando apenas dois ponteiros?

Eu me pergunto se existe alguma lógica para reverter uma lista vinculada de forma simples usando apenas dois ponteiros.

O que se segue é usado para inverter a lista encadeada único usando três ponteiros nomeadamente 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 alguma outra alternativa para reverter a lista vinculada? Qual seria a melhor lógica para reverter uma lista unida individualmente, em termos de complexidade de tempo?

Alguma alternativa? Não, isso é o mais simples possível e não há uma maneira fundamentalmente diferente de fazer isso. Este algoritmo já está no tempo O (n), e você não pode ficar mais rápido do que isso, pois você deve modificar cada nó.

Parece que seu código está no caminho certo, mas não está funcionando bem no formulário acima. Esta é uma versão funcional:

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

Eu odeio ser o portador de más notícias, mas não acho que sua solução de três pontos realmente funcione. Quando o usei no seguinte equipamento de teste, a lista foi reduzida a um nó, conforme a seguinte saída:

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

Você não obterá complexidade de tempo melhor do que sua solução, pois é O (n) e você precisa visitar todos os nós para alterar os ponteiros, mas você pode fazer uma solução com apenas dois ponteiros extras facilmente, conforme mostrado no código a seguir:

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

Este código resulta em:

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

que eu acho que é o que você estava procurando. Na verdade, ele pode fazer isso, pois, uma vez carregado firstno ponteiro que percorre a lista, você pode reutilizá-lo firstà vontade.

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

Aqui está o código para inverter uma lista vinculada isoladamente em C .

E aqui está colado abaixo:

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

Sim. Tenho certeza de que você pode fazer isso da mesma forma que troca dois números sem usar um terceiro . Simplesmente lance os ponteiros para int / long e execute a operação XOR algumas vezes. Esse é um daqueles truques de C que tornam a pergunta divertida, mas não tem nenhum valor prático.

Você pode reduzir a complexidade de O (n)? Não, na verdade não. Basta usar uma lista duplamente vinculada se achar que vai precisar da ordem inversa.

Robert Sedgewick, " Algorithms in C ", Addison-Wesley, 3ª edição, 1997, [Seção 3.4]

Caso não seja uma lista cíclica, então NULL é o último link.

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

Apenas por diversão (embora a otimização da recursão da cauda deva impedi-la de consumir toda a pilha):

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

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

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

root = reverse(root, NULL);

Para trocar duas variáveis ​​sem o uso de uma variável temporária,

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

a maneira mais rápida é escrever em uma linha

a = a ^ b ^ (b=a)

Similarmente,

usando duas trocas

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

solução usando xor

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

solução em uma linha

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

A mesma lógica é usada para reverter uma lista vinculada.

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

Você precisa de um ponteiro de trilha que rastreará a lista.

Você precisa de duas dicas:

primeiro ponteiro para escolher o primeiro nó. segundo ponteiro para escolher o segundo nó.

Em processamento :

Ponteiro para mover trilha

Aponte o segundo nó para o primeiro nó

Mova o primeiro ponteiro um passo, atribuindo o segundo ponteiro a um

Mova o segundo ponteiro um passo, atribuindo o ponteiro da trilha ao segundo

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;

}

Que tal o mais legível:

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

Aqui está uma versão mais simples em Java. Ele usa apenas dois ponteiros curreprev

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
}

Calcule a complexidade de tempo do algoritmo que você está usando agora e ficará óbvio que não pode ser melhorado.

Não entendo por que é necessário voltar à cabeça, já que estamos passando isso como argumento. Estamos passando o chefe da lista de links, então podemos atualizar também. Abaixo está uma solução simples.

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

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

Não, nada mais rápido do que o O (n) atual pode ser feito. Você precisa alterar cada nó, então o tempo será proporcional ao número de elementos de qualquer maneira e isso é O (n) que você já tem.

Usar dois ponteiros enquanto mantém a complexidade de tempo de O (n), o mais rápido possível, só pode ser possível por meio da conversão de números de ponteiros e troca de seus valores. Aqui está uma implementação:

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

Eu tenho uma abordagem um pouco diferente. Eu queria fazer uso das funções existentes (como insert_at (índice), delete_from (índice)) para inverter a lista (algo como uma operação de deslocamento à direita). A complexidade ainda é O (n), mas a vantagem é o código mais reutilizado. Dê uma olhada no método another_reverse () e deixe-me saber o que vocês pensam.

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

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

Sim, existe uma maneira de usar apenas dois ponteiros. Isto é, criando uma nova lista encadeada onde o primeiro nó é o primeiro nó da lista fornecida e o segundo nó da primeira lista é adicionado no início da nova lista e assim por diante.

Aqui está minha versão:

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

Onde

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

Estou usando java para implementar isso e a abordagem é o desenvolvimento dirigido por teste, portanto, os casos de teste também estão anexados.

A classe Node que representa um único nó -

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 serviço que recebe o nó inicial como entrada e o reserva sem usar espaço extra.

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 o caso de teste que cobre o cenário acima. Observe que você precisa de jarros junit. Estou usando testng.jar; você pode usar o que quiser ..

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


    }
}

Um algoritmo simples se você usar a lista vinculada como uma estrutura de pilha:

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

}

O desempenho pode ser afetado desde a chamada de função adicional para add e malloc, de modo que os algoritmos de trocas de endereço são melhores, mas aquele realmente cria uma nova lista para que você possa usar opções adicionais como classificar ou remover itens se adicionar uma função de retorno de chamada como parâmetro para o reverter.

Aqui está uma abordagem um pouco diferente, mas simples em 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;
}

Saída aqui

A seguir está uma implementação usando 2 ponteiros (cabeça e 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;
}

aqui está uma pequena solução simples ...

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

Você pode ter solução deste problema com a ajuda de apenas um ponteiro extra, que deve ser estático para a função reversa. Está em complexidade 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;
    }
}

Como alternativa, você pode usar recursão-

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

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

    }


}