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

109

Zastanawiam się, czy istnieje jakaś logika odwracania pojedynczo połączonej listy przy użyciu tylko dwóch wskaźników.

Dodaje stosuje się odwrócić jedną listę łączy się stosując trzy wskaźniki mianowicie 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;
}

Czy istnieje inna alternatywa do odwrócenia połączonej listy? Jaka byłaby najlepsza logika do odwrócenia pojedynczo połączonej listy pod względem złożoności czasowej?

Madhan
źródło
1
możliwy duplikat: stackoverflow.com/questions/818443/ ...
kajaco
3
Niezupełnie, to raczej dwie kolejki niż dwa wskaźniki.
paxdiablo
7
Ponieważ jesteś tutaj, aby pomóc, a nie grać w grę rep?
GManNickG
1
GMan: w tym rzecz, nie jestem pewien, czy pomagam komukolwiek, nawet jemu, jeśli nie może tego zrobić.
1
Pomagasz tym z nas, którzy czytają i wyciągają wnioski z pytań i odpowiedzi. Uznałem to za wnikliwe.
Andrew Coleson

Odpowiedzi:

133

Jakaś alternatywa? Nie, to jest tak proste, jak to tylko możliwe, i nie ma zasadniczo innego sposobu, aby to zrobić. Ten algorytm ma już czas O (n) i nie możesz uzyskać nic szybszego, ponieważ musisz zmodyfikować każdy węzeł.

Wygląda na to, że Twój kod jest na dobrej drodze, ale nie działa w powyższym formularzu. Oto działająca wersja:

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

źródło
Nie jestem pewien co do „oczywistych błędów” w oryginale. Jeśli chodzi o projekt, nie przechodzenie przez pierwszą część listy i nie zwracanie nowej głowy to zły pomysł. Jedynym błędem jest jednak to, że ostatnia linia reverse()funkcji powinna być ustawiana jako pierwsza, jak sądzę. W przeciwnym razie oryginalny kod działał poprawnie po podłączeniu do zgrabnej wiązki testowej. Mimo to otrzymujesz ode mnie +1 - ale wyjaśnienie, co uważasz za „oczywiste błędy”, poprawiłoby Twoją odpowiedź.
Jonathan Leffler
2
Czy w powyższym kodzie nie ma błędu? Wewnątrz pętli while za każdym razem tworzysz nowy wskaźnik „następny”. Więc jeśli na połączonej liście jest N węzłów, tworzysz N nowych wskaźników i nie zwalniasz ich ani nie usuwasz. Myślę, że byłoby dobrze, gdybyś utworzył wskaźnik „next” przed pętlą while i po prostu dokonał przypisania „next = root-> next” wewnątrz pętli while.
aks
6
@aks: nie ma wycieku. Zwróć uwagę na malloc / etc. nie są nazywane, więc nie ma potrzeby, aby je uwolnić. Zakres zmiennej „next” obejmuje pętlę, ale to jest w porządku.
1
Nawet jeśli nie ma przecieku, jaka jest potrzeba deklarowania następnego za każdym razem, jak wspomniał aks, „byłoby dobrze, gdyby utworzyłeś wskaźnik„ next ”przed pętlą while i po prostu dokonał przypisania„ next = root-> next 'wewnątrz pętli while. ”, prawda?
GeekyJ
1
Podoba mi się twoje dosłowne listy z linkami, to miłe.
43

Nienawidzę być zwiastunem złych wiadomości, ale nie sądzę, aby twoje rozwiązanie za trzy wskazówki faktycznie działało. 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 czasowej niż twoje rozwiązanie, ponieważ jest to O (n) i musisz odwiedzić każdy węzeł, aby zmienić wskaźniki, ale możesz łatwo zrobić rozwiązanie z tylko dwoma dodatkowymi wskaźnikami, 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;
}

Ten kod wyprowadza:

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

co myślę, że to jest to, czego szukałeś. W rzeczywistości może to zrobić, ponieważ po załadowaniu firstwskaźnika do wskaźnika przechodzącego przez listę możesz ponownie użyć firstdo woli.

paxdiablo
źródło
2
Bardzo elegancko. Ponowne wykorzystanie firstwskaźnik na samej liście połączonej rozwiązanie pozwala używać tylko 2 dodatkowe wskaźniki, ale 3 łączne wskaźniki są nadal niezbędne do tego.
Kevin Kibler
Używasz do tego pierwszego, curNode i nxtNode, łącznie trzech wskaźników. dlaczego to jest rozwiązanie dwukierunkowe?
Yashasvi
@Yash, przeczytaj jeszcze raz, dwa dodatkowe wskaźniki na górze first. W ten sam sposób rozwiązanie trzech wskaźnik PO miała first, p, qi r.
paxdiablo
@paxdiablo oh! mój błąd. Przepraszam, źle zrozumiałem pytanie. Dzięki :)
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;
}
splicer
źródło
2
Witaj! Wiem, że to pytanie jest stare, ale czy mógłbyś wyjaśnić, co dzieje się w tej funkcji i dlaczego działa. :) Dzięki!
MakeTheTrumpetsBlow
13

Oto kod, aby odwrócić pojedynczo połączonej listy 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;
}
ma11hew28
źródło
4
Dzięki za niesamowitą
grafikę
3

Tak. Jestem pewien, że możesz to zrobić w ten sam sposób , w jaki możesz zamienić dwie liczby bez używania trzeciej . Po prostu rzuć wskaźniki na int / long i wykonaj operację XOR kilka razy. To jedna z tych sztuczek C, która jest zabawnym pytaniem, ale nie ma żadnej praktycznej wartości.

Czy możesz zmniejszyć złożoność O (n)? Nie, nie bardzo. Po prostu użyj podwójnie połączonej listy, jeśli myślisz, że będziesz potrzebować odwrotnej kolejności.

brianegge
źródło
… I jeśli nie będziesz ostrożny, rodzi się nowy problem ze zgodnością 64-bitową. W ten sposób też nie kupisz żadnego występu.
LnxPrgr3
2
Nie wpłynie to na złożoność czasową - to znaczy, nie sprawi, że rozwiązanie będzie lepsze niż czas liniowy. Chodzi mi o to, że możesz zaoszczędzić 4 lub 8 bajtów pamięci, ale to nie zmieni ogólnej złożoności algorytmu.
poundifdef
@rascher, złożoność czasowa była drugą częścią pytania. Pierwsza część dotyczyła zmniejszenia liczby wymaganych wskaźników.
paxdiablo
2
Myślę, że oryginalny plakat szukał taniej sztuczki C. Z mojego doświadczenia - i sprofilowałem to :) - typowe sztuczki unikające pośrednika są w rzeczywistości wolniejsze niż zwykłe użycie pośrednika.
Będzie
Link jest uszkodzony, ale jestem pewien, że zamiana 2 liczb za pomocą XOR jest oldschoolowa :)
Dane
3

Robert Sedgewick, „ Algorithms in C ”, Addison-Wesley, 3. wydanie, 1997, [sekcja 3.4]

W przypadku, gdy nie jest to lista cykliczna, dlatego NULL jest ostatnim łączem.

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
źródło
3

Dla zabawy (chociaż optymalizacja rekurencji ogona powinna powstrzymać ją przed zjadaniem całego stosu):


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
źródło
2
Myślę, że „powinienem” to trochę przesadzić. Twój kompilator C „może” przeprowadzić optymalizację wywołań ogonowych i łatwo jest sprawdzić dla danego kompilatora / opcji, czy to robi, czy nie: spójrz na dezasemblację. Lub daj mu kilka milionów węzłów i zobacz, czy się zawiesza ;-)
Steve Jessop
3

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,

za pomocą dwóch zamian

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

rozwiązanie przy użyciu xor

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

rozwiązanie 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 służy do odwracania 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;
}  
sr01853
źródło
1
Zakłada się, że int jest tego samego rozmiaru co wskaźnik, nie będzie działać na systemach amd64 (można użyć intptr_t). Chociaż interesujące - zamiana w ten sposób jest nieoptymalna w nowoczesnych systemach.
ideasman42,
3

Potrzebujesz wskaźnika ścieżki, który będzie śledził listę.

Potrzebujesz dwóch wskazówek:

pierwszy wskaźnik, aby wybrać pierwszy węzeł. drugi wskaźnik, aby wybrać drugi węzeł.

Przetwarzanie:

Przesuń wskaźnik ścieżki

Skieruj drugi węzeł na pierwszy węzeł

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 drugiego

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
źródło
2

A co z bardziej czytelnymi:


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
źródło
2

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
}
ernesto
źródło
Pytanie dotyczy rozwiązania C, a nie Java
Degustaf
1
Pytanie dotyczy raczej wykonywania operacji odwrotnej tylko z dwoma dodatkowymi wskaźnikami (lub referencjami). Niezależnie od tego, czy jest to C czy Java, logika jest taka sama.
ernesto
1

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

John La Rooy
źródło
1

Nie rozumiem, dlaczego istnieje potrzeba powrotu głowy, skoro przekazujemy to jako argument. Przechodzimy obok listy linków, a następnie możemy zaktualizować. Poniżej 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;
}
Hardik Chauhan
źródło
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
źródło
0

Nie, nie da się zrobić nic szybciej niż obecne O (n). 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.

ostry
źródło
0

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

#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
źródło
0

Mam trochę inne podejście. Chciałem skorzystać z istniejących funkcji (takich jak insert_at (indeks), delete_from (indeks)), aby odwrócić listę (coś w rodzaju operacji przesunięcia w prawo). Złożoność jest nadal O (n), ale zaletą jest więcej ponownie wykorzystanego kodu. Rzuć okiem na metodę another_reverse () i daj 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;
}
FunBoy
źródło
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
źródło
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);
}
Pan Amit Kumar
źródło
Skontaktuj się ze mną w sprawie implementacji języka C.
Pan Amit Kumar
0

Tak, jest sposób wykorzystujący tylko dwa wskaźniki. To znaczy, tworząc nową połączoną listę, w której pierwszy węzeł jest pierwszym węzłem z danej listy, a drugi węzeł pierwszej listy jest dodawany na początku nowej listy i tak dalej.

deepak verma
źródło
0

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;
};
cpp
źródło
0

Używam javy do implementacji tego, a podejście jest oparte na testach, dlatego dołączone są również przypadki testowe.

Klasa Node, która reprezentuje 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ługi, która przyjmuje węzeł początkowy jako dane wejściowe i rezerwuje go bez używania dodatkowego miejsca.

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


}

I przypadek testowy, który obejmuje powyższy scenariusz. Pamiętaj, że potrzebujesz słoików junit. Używam testng.jar; możesz użyć wszystkiego, 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();
        }


    }
}
Mohammad Adnan
źródło
0

Prosty algorytm, jeśli używasz połączonej listy 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 ulec pogorszeniu, ponieważ dodatkowe wywołanie funkcji do add i malloc, więc algorytmy zamiany adresów są lepsze, ale faktycznie tworzy nową listę, więc możesz użyć dodatkowych opcji, takich jak sortowanie lub usuwanie elementów, jeśli dodasz funkcję zwrotną jako parametr do odwrócić.

Ilian Zapryanov
źródło
0

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

Wyjście tutaj

Carl
źródło
0

Poniżej znajduje się jedna implementacja wykorzystująca 2 wskaźniki (nagłówek 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;
}
ŁUK
źródło
Choć może to być sprytne i nieczytelne, masz kłopoty, jeśli sizeof(size_t) < sizeof(ListNode*)... powinieneś użyć std::uintptr_t.
Quentin,
0

oto małe 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;
        }       
   }
 }
waqar ahmed
źródło
0

Możesz rozwiązać ten problem za pomocą tylko jednego dodatkowego wskaźnika, który musi być statyczny dla funkcji odwrotnej. Jest w złożoności 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
źródło
0

Alternatywnie 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;
}
vaibhav
źródło
Jak to jest poprawne. Używasz więcej niż dwóch wskaźników, jest on po prostu ukryty na stosie za każdym razem, gdy wykonujesz wywołanie funkcji.
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
źródło
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
źródło
węzeł nie jest wskaźnikiem, po prostu przekazujemy głowę jako węzeł. Daj mi znać, jeśli potrzebujesz więcej wyjaśnień
Raju Muke