Wie kann man eine einfach verknüpfte Liste mit nur zwei Zeigern umkehren?

109

Ich frage mich, ob es eine Logik gibt, eine einfach verknüpfte Liste mit nur zwei Zeigern umzukehren.

Im Folgenden wird die einzelne verknüpfte Liste mit drei Zeigern nämlich umkehren 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;
}

Gibt es eine andere Alternative, um die verknüpfte Liste umzukehren? Was wäre die beste Logik, um eine einfach verknüpfte Liste in Bezug auf die Zeitkomplexität umzukehren?

Madhan
quelle
1
Mögliches Duplikat: stackoverflow.com/questions/818443/…
kajaco
3
Nicht wirklich, das sind eher zwei Warteschlangen als zwei Zeiger.
Paxdiablo
7
Weil du hier bist, um zu helfen und kein Wiederholungsspiel zu spielen?
GManNickG
1
GMan: Das ist die Sache, ich bin mir nicht sicher, ob ich jemandem helfe, auch ihm, wenn er nicht durchkommen kann.
1
Sie helfen denen von uns, die lesen und etwas aus den Fragen und Antworten herausholen. Ich fand es aufschlussreich.
Andrew Coleson

Antworten:

133

Irgendeine Alternative? Nein, das ist so einfach wie es nur geht und es gibt keinen grundlegend anderen Weg, dies zu tun. Dieser Algorithmus ist bereits O (n) -Zeit und Sie können nicht schneller werden, da Sie jeden Knoten ändern müssen.

Es sieht so aus, als ob Ihr Code auf dem richtigen Weg ist, aber in der obigen Form funktioniert er nicht ganz. Hier ist eine Arbeitsversion:

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

quelle
Ich bin mir nicht sicher über "offensichtliche Fehler" im Original. In Bezug auf das Design ist es eine schlechte Idee, den Kopf der Liste nicht weiterzugeben und den neuen Kopf nicht zurückzugeben. Der einzige Fehler ist jedoch, dass die letzte Zeile in der reverse()Funktion zuerst eingestellt werden sollte, glaube ich. Andernfalls funktionierte der ursprüngliche Code einwandfrei, wenn er an Ihr ordentliches Testkabel angeschlossen wurde. Sie erhalten trotzdem +1 von mir - aber eine Erklärung dessen, was Sie als "offensichtliche Fehler" betrachten, würde Ihre Antwort verbessern.
Jonathan Leffler
2
Gibt es nicht einen Fehler im obigen Code? Innerhalb der while-Schleife erstellen Sie jedes Mal einen neuen 'nächsten' Zeiger. Wenn die verknüpfte Liste also N Knoten enthält, erstellen Sie N neue Zeiger und geben sie nicht frei oder löschen sie nicht. Ich denke, es wäre richtig, wenn Sie den 'next'-Zeiger vor der while-Schleife erstellen und einfach die Zuweisung' next = root-> next 'innerhalb der while-Schleife vornehmen.
Aks
6
@aks: Es gibt kein Leck. Beachten Sie malloc / etc. werden nicht aufgerufen, so dass keine Notwendigkeit besteht, sich zu befreien. Die Variable 'next' ist auf die Schleife beschränkt, aber das ist vollkommen in Ordnung.
1
Selbst wenn es kein Leck gibt, was ist die Notwendigkeit, jedes Mal das nächste Mal zu deklarieren, wie bereits erwähnt, "es wäre richtig, wenn Sie den 'nächsten' Zeiger vor der while-Schleife erstellen und einfach die Zuweisung 'next = root-> next vornehmen 'innerhalb der while-Schleife. ", nicht wahr?
GeekyJ
1
Ich mag Ihre verknüpften Listenliterale, das ist ordentlich.
43

Ich hasse es, schlechte Nachrichten zu überbringen, aber ich glaube nicht, dass Ihre Drei-Zeiger-Lösung tatsächlich funktioniert. Als ich es im folgenden Testkabel verwendete, wurde die Liste gemäß der folgenden Ausgabe auf einen Knoten reduziert:

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

Sie erhalten keine bessere Zeitkomplexität als Ihre Lösung, da es O (n) ist und Sie jeden Knoten besuchen müssen, um die Zeiger zu ändern. Sie können jedoch ganz einfach eine Lösung mit nur zwei zusätzlichen Zeigern erstellen, wie im folgenden Code gezeigt:

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

Dieser Code gibt aus:

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

was ich denke, ist das, wonach du gesucht hast. Dies ist tatsächlich möglich, da Sie nach dem Laden firstin den Zeiger, der die Liste durchläuft, firstnach Belieben wiederverwenden können .

paxdiablo
quelle
2
Sehr elegant. Durch die Wiederverwendung des firstZeigers in der verknüpften Liste selbst kann die Lösung nur 2 zusätzliche Zeiger verwenden, dafür sind jedoch noch 3 Gesamtzeiger erforderlich.
Kevin Kibler
Sie verwenden zuerst curNode und nxtNode, insgesamt drei Zeiger dafür. Wie kommt es, dass dies eine Zwei-Zeiger-Lösung ist?
Yashasvi
@ Yash, nochmal lesen, zwei zusätzliche Zeiger oben drauf first. Auf die gleiche Weise die Drei-Zeiger - Lösung OP hatte first, p, qund r.
Paxdiablo
@paxdiablo oh! mein Fehler. Entschuldigung, ich habe die Frage falsch verstanden. Danke :)
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;
}
Spleißer
quelle
2
Hallo! Ich weiß, dass diese Frage alt ist, aber würde es Ihnen etwas ausmachen zu erklären, was in dieser Funktion passiert und warum sie funktioniert. :) Vielen Dank!
MakeTheTrumpetsBlow
13

Hier ist der Code , um eine einzeln verknüpfte Liste in C umgekehrt .

Und hier wird es unten eingefügt:

// 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
quelle
4
Vielen Dank für die tolle ASCII-Kunst für die Erklärung :)
Achedeuzot
3

Ja. Ich bin sicher, Sie können dies genauso tun, wie Sie zwei Zahlen tauschen können, ohne eine dritte zu verwenden . Setzen Sie die Zeiger einfach auf int / long und führen Sie die XOR-Operation einige Male aus. Dies ist einer dieser C-Tricks, die für eine lustige Frage sorgen, aber keinen praktischen Wert haben.

Können Sie die O (n) -Komplexität reduzieren? Nein nicht wirklich. Verwenden Sie einfach eine doppelt verknüpfte Liste, wenn Sie glauben, dass Sie die umgekehrte Reihenfolge benötigen.

Brianegge
quelle
… Und ein neues 64-Bit-Kompatibilitätsproblem entsteht, wenn Sie nicht vorsichtig sind. Es ist auch unwahrscheinlich, dass Sie auf diese Weise eine Leistung kaufen.
LnxPrgr3
2
Dies hat keinen Einfluss auf die Zeitkomplexität - das heißt, die Lösung wird nicht besser als die lineare Zeit. Ich meine, Sie könnten 4 oder 8 Bytes Speicher sparen, aber das ändert nichts an der Gesamtkomplexität des Algorithmus.
Poundifdef
@rascher, Zeitkomplexität war der zweite Teil der Frage. Der erste Teil hatte mit der Reduzierung der Anzahl der erforderlichen Zeiger zu tun.
Paxdiablo
2
Ich denke, das Originalplakat suchte nach einem billigen C-Trick. Nach meiner Erfahrung - und ich habe es profiliert :) - sind die typischen Tricks zur Vermeidung von Vermittlern tatsächlich langsamer als nur die Verwendung eines Vermittlers.
Will
Die Verbindung ist unterbrochen, aber ich bin sicher, dass das Austauschen von 2 Nummern mit XOR altmodisch ist :)
Dane
3

Robert Sedgewick, " Algorithmen in C ", Addison-Wesley, 3. Auflage, 1997, [Abschnitt 3.4]

Falls dies keine zyklische Liste ist, ist NULL der letzte 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; }

Limitcracker
quelle
3

Nur zum Spaß (obwohl die Optimierung der Schwanzrekursion verhindern sollte, dass der gesamte Stapel verschlungen wird):


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
quelle
2
Ich denke, "sollte" übertreibt den Fall ein wenig. Ihr C-Compiler "könnte" eine Tail-Call-Optimierung durchführen, und es ist einfach genug, nach einem bestimmten Compiler / bestimmten Optionen zu suchen, ob dies der Fall ist oder nicht: Sehen Sie sich die Disassemblierung an. Oder geben Sie ihm ein paar Millionen Knoten und sehen Sie, ob es abstürzt ;-)
Steve Jessop
3

Um zwei Variablen ohne Verwendung einer temporären Variablen auszutauschen,

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

Der schnellste Weg ist, es in eine Zeile zu schreiben

a = a ^ b ^ (b=a)

Ähnlich,

mit zwei Swaps

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

Lösung mit xor

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

Lösung in einer Zeile

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

Dieselbe Logik wird verwendet, um eine verknüpfte Liste umzukehren.

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
quelle
1
Dies setzt voraus, dass ein int die gleiche Größe wie ein Zeiger hat und auf amd64-Systemen (die Sie verwenden könnten intptr_t) nicht funktioniert . Interessant - auf diese Weise zu tauschen ist auf modernen Systemen nicht optimal.
ideasman42
3

Sie benötigen einen Spurzeiger, der die Liste verfolgt.

Sie benötigen zwei Zeiger:

erster Zeiger zum Auswählen des ersten Knotens. zweiter Zeiger zur Auswahl des zweiten Knotens.

Wird bearbeitet :

Spurzeiger verschieben

Zeigen Sie mit dem zweiten Knoten auf den ersten Knoten

Bewegen Sie den ersten Zeiger um einen Schritt, indem Sie einem den zweiten Zeiger zuweisen

Bewegen Sie den zweiten Zeiger um einen Schritt, indem Sie dem zweiten den Spurzeiger zuweisen

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
quelle
2

Wie wäre es mit dem besser lesbaren:


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
quelle
2

Hier ist eine einfachere Version in Java. Es werden nur zwei Zeiger curr& verwendetprev

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
quelle
Die Frage ist nach einer C-Lösung, nicht nach einer in Java
Degustaf
1
Die Frage bezieht sich eher auf die umgekehrte Operation mit nur zwei zusätzlichen Zeigern (oder Referenzen). Ob C oder Java, die Logik ist dieselbe.
ernesto
1

Berechnen Sie die zeitliche Komplexität des Algorithmus, den Sie jetzt verwenden, und es sollte offensichtlich sein, dass er nicht verbessert werden kann.

John La Rooy
quelle
1

Ich verstehe nicht, warum es notwendig ist, den Kopf zurückzugeben, da wir ihn als Argument übergeben. Wir übergeben den Kopf der Linkliste, dann können wir auch aktualisieren. Unten ist eine einfache Lösung.

#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
quelle
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
quelle
0

Nein, nichts schnelleres als das aktuelle O (n) kann getan werden. Sie müssen jeden Knoten ändern, damit die Zeit ohnehin proportional zur Anzahl der Elemente ist und das ist O (n), das Sie bereits haben.

scharfer Zahn
quelle
0

Die Verwendung von zwei Zeigern unter Beibehaltung der Zeitkomplexität von O (n), die am schnellsten erreichbar ist, ist möglicherweise nur durch Zahlenumwandlung von Zeigern und Vertauschen ihrer Werte möglich. Hier ist eine Implementierung:

#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
quelle
0

Ich habe einen etwas anderen Ansatz. Ich wollte die vorhandenen Funktionen (wie insert_at (Index), delete_from (Index)) nutzen, um die Liste umzukehren (so etwas wie eine Rechtsverschiebungsoperation). Die Komplexität ist immer noch O (n), aber der Vorteil ist mehr wiederverwendeter Code. Schauen Sie sich eine andere_reverse () -Methode an und lassen Sie mich wissen, was Sie alle denken.

#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;
}
Lustiger Bub
quelle
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
quelle
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);
}
Herr Amit Kumar
quelle
Kontaktieren Sie mich für die C-Implementierung eines Problems.
Herr Amit Kumar
0

Ja, es gibt eine Möglichkeit, nur zwei Zeiger zu verwenden. Dies geschieht durch Erstellen einer neuen verknüpften Liste, wobei der erste Knoten der erste Knoten der angegebenen Liste ist und der zweite Knoten der ersten Liste am Anfang der neuen Liste hinzugefügt wird und so weiter.

Deepak Verma
quelle
0

Hier ist meine Version:

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

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

wo

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
quelle
0

Ich verwende Java, um dies zu implementieren, und der Ansatz ist eine testgetriebene Entwicklung, daher sind auch Testfälle beigefügt.

Die Knotenklasse, die einen einzelnen Knoten darstellt -

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

Serviceklasse, die den Startknoten als Eingabe verwendet und ohne zusätzlichen Speicherplatz reserviert.

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


}

Und der Testfall, der das obige Szenario abdeckt. Bitte beachten Sie, dass Sie Junit-Gläser benötigen. Ich benutze testng.jar; Sie können alles verwenden, was Ihnen gefällt.

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
quelle
0

Ein einfacher Algorithmus, wenn Sie die verknüpfte Liste als Stapelstruktur verwenden:

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

}

Die Leistung kann beeinträchtigt werden, da zusätzliche Funktionen für add und malloc aufgerufen werden, sodass die Algorithmen für Adressentausch besser sind, diese jedoch tatsächlich eine neue Liste erstellt, sodass Sie zusätzliche Optionen wie das Sortieren oder Entfernen von Elementen verwenden können, wenn Sie der Funktion eine Rückruffunktion als Parameter hinzufügen umkehren.

Ilian Zapryanov
quelle
0

Hier ist ein etwas anderer, aber einfacher Ansatz in 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;
}

Ausgabe hier

Carl
quelle
0

Es folgt eine Implementierung mit 2 Zeigern (head und 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;
}
BOGEN
quelle
So klug und nicht entzifferbar das auch sein mag, Sie sind in Schwierigkeiten, wenn sizeof(size_t) < sizeof(ListNode*)... Sie verwenden sollten std::uintptr_t.
Quentin
0

Hier ist eine kleine einfache Lösung ...

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
quelle
0

Sie können dieses Problem mit nur einem zusätzlichen Zeiger lösen, der für die Umkehrfunktion statisch sein muss. Es ist in O (n) Komplexität.

#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
quelle
0

Alternativ können Sie die Rekursion verwenden.

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
quelle
Wie ist das richtig? Sie verwenden mehr als zwei Zeiger, die bei jedem Funktionsaufruf nur auf dem Stapel ausgeblendet werden.
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
quelle
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
quelle
Knoten ist kein Zeiger. Wir haben nur den Kopf als Knoten übergeben. Lassen Sie mich wissen, wenn Sie weitere
Erläuterungen