Jak odwrócić pojedynczo połączoną listę używając tylko dwóch wskaźników?

Nie chcę przynosić złych wieści, ale twoje trzypunktowe rozwiązanie nie działa. Kiedy użyłem go w poniższej wiązce testowej, lista została zredukowana do jednego węzła, zgodnie z następującym wyjściem:

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

Nie uzyskasz lepszej złożoności czasu niż rozwiązanie, ponieważ jest O(n) i musisz odwiedzić każdy węzeł, aby zmienić wskaźniki, ale możesz zrobić rozwiązanie z tylko dwoma dodatkowymi wskaźnikami dość łatwo, jak pokazano w poniższym kodzie:

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

To kod wyjścia:

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

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

Oto kod Odwróć pojedynczo połączoną listę w C .

I tutaj jest wklejony poniżej:

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

Tak. Jestem pewien, że możesz to zrobić w ten sam sposób możesz zamienić dwie liczby bez użycia trzeciej . Wystarczy rzucić wskaźniki do int / long i wykonać operację XOR kilka razy. Jest to jedna z tych sztuczek C, która sprawia, że Zabawne pytanie, ale nie ma żadnej praktycznej wartości.

Czy można zmniejszyć złożoność O (n)? Nie, Nie bardzo. Wystarczy użyć podwójnie połączonej listy, jeśli uważasz, że będziesz potrzebował odwrotnej kolejności.

Robert Sedgewick, "algorytmy w C", Addison-Wesley, wydanie 3, 1997, [sekcja 3.4]

W przypadku, gdy nie jest to lista cykliczna, stąd NULL jest ostatnim odnośnikiem.

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

Tak dla zabawy (chociaż optymalizacja rekurencji ogonowej powinna przestać zżerać cały stos):

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

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

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

root = reverse(root, NULL);

Aby zamienić dwie zmienne bez użycia zmiennej tymczasowej,

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

Najszybszym sposobem jest zapisanie go w jednej linii

a = a ^ b ^ (b=a)

Podobnie,

Używanie dwóch swapów

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

Rozwiązanie za pomocą xor

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

Roztwór w jednej linii

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

Ta sama logika jest używana do odwrócenia połączonej listy.

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

Potrzebujesz Wskaźnik ścieżki , który będzie śledzić listę.

Potrzebujesz dwóch wskazówek:

Pierwszy wskaźnik do wybrania pierwszego węzła. drugi wskaźnik do wybrania drugiego węzła.

Przetwarzanie:

Move Track Pointer

Point second node to first node

Przesuń pierwszy wskaźnik o jeden krok, przypisując drugi wskaźnik do jednego

Przesuń drugi wskaźnik o jeden krok, przypisując wskaźnik ścieżki do drugi

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;

}

A może bardziej czytelne:

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

Oto prostsza wersja w Javie. Używa tylko dwóch wskaźników curr & 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
}

Nie rozumiem, dlaczego istnieje potrzeba powrotu głowy, ponieważ przekazujemy to jako argument. Mijamy głowę listy linków, wtedy możemy również zaktualizować. Poniżej znajduje się proste rozwiązanie.

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

Wypracuj złożoność czasową algorytmu, którego teraz używasz i powinno być oczywiste, że nie można go poprawić.

Nie, nic szybszego niż obecne O (n) nie może być zrobione. Musisz zmienić każdy węzeł, więc czas i tak będzie proporcjonalny do liczby elementów i to jest O (n), które już masz.

Używanie dwóch wskaźników przy zachowaniu złożoności czasowej O(n), najszybszego możliwego do osiągnięcia, może być możliwe tylko poprzez rzucanie liczbami wskaźników i zamianę ich wartości. Oto implementacja:

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

Mam nieco inne podejście. Chciałem skorzystać z istniejących funkcji (takich jak insert_at(index), delete_from (index)), aby odwrócić listę (coś w rodzaju operacji przesunięcia w prawo). Złożoność jest nadal O (n), ale zaletą jest bardziej ponownie użyty kod. Rzućcie okiem na inną metodę_reverse () i dajcie mi znać, co myślicie.

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

Tak, istnieje sposób, w którym używa się tylko dwóch wskaźników. Oznacza to utworzenie nowej listy połączonej, gdzie pierwszy węzeł jest pierwszym węzłem danej listy, a drugi węzeł pierwszej listy jest dodawany na początku nowej listy i tak dalej.

Oto moja wersja:

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

Gdzie

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

Używam Javy, aby to zaimplementować i podejście jest test driven development, stąd dołączone są również przypadki testowe.

Klasa węzła reprezentująca pojedynczy węzeł-

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

Klasa usług, która pobiera węzeł start jako wejście i rezerwuje go bez użycia dodatkowej przestrzeni.

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


}

Oraz przypadku testowego, który obejmuje powyższy scenariusz. Pamiętaj, że potrzebujesz słoików junit. Używam testng.słoik; możesz użyć każdego, co ci się podoba..

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


    }
}

Prosty algorytm, jeśli używasz listy połączonej jako struktury stosu:

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

}

Wydajność może mieć wpływ od dodatkowego wywołania funkcji do add i malloc więc algorytmy swapów adresów są lepsze, ale ten jeden faktycznie tworzy nową listę, więc można użyć dodatkowych opcji, takich jak sortowanie lub usuwanie elementów, jeśli dodasz funkcję zwrotną jako parametr do tyłu.

Oto nieco inne, ale proste podejście w 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;
}

Output here

Poniżej znajduje się jedna implementacja wykorzystująca 2 wskaźniki (head i 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;
}

Oto proste rozwiązanie...

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

Możesz rozwiązać ten problem za pomocą tylko jednego dodatkowego wskaźnika, który musi być statyczny dla funkcji odwrotnej. Jest w O (N) złożoności.

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

Jako alternatywę możesz użyć rekurencji -

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

Rozwiązanie przy użyciu 1 zmiennej (tylko 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;