Wie reverse eine einfach verknüpfte Liste mit nur zwei Zeiger?

Ich würde gefragt, wenn es gibt ein paar Logik eine Umkehrung der verlinkten Liste mit nur zwei Zeigern.

Folgenden wird verwendet, um reverse die einfach verkettete Liste mit drei Zeigern, nämlich p, q, r:

struct node
{
    int data;
    struct node *link;
};

void reverse()
{
    struct node *p = first,
                *q = NULL,
                *r;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    q = first;
}

Gibt es irgendeine andere Alternative zum umkehren der verlinkten Liste? was wäre die beste Logik umkehren eine einfach verknüpfte Liste, in Bezug auf die Zeit-Komplexität?

InformationsquelleAutor der Frage Madhan | 2009-11-26

  1. 131

    Alternative? Nein, dies ist so einfach, wie es kommt, und es gibt keine grundsätzlich-anderen Weg, es zu tun. Dieser Algorithmus ist bereits O(n) Zeit, und man kann nicht schneller als das, wie Sie ändern müssen alle Knoten.

    Es sieht aus wie Sie Ihren code auf der richtigen Spur, aber es ist nicht ganz der Arbeit in das Formular. Hier eine funktionierende version:

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

    InformationsquelleAutor der Antwort

  2. 45

    Ich hasse es der überbringer schlechter Nachrichten, aber ich glaube nicht, dass Ihr drei-Zeiger-Lösung tatsächlich funktioniert. Wenn ich es in der folgenden Testumgebung, die Liste wurde reduziert auf einen Knoten, wie pro die folgende Ausgabe:

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

    Bekommen Sie keine bessere Zeit-Komplexität als Ihre Lösung, denn es ist O(n) und haben Sie zu besuchen, alle Knoten zu ändern, die Zeiger, aber Sie kann tun, eine Lösung mit nur zwei zusätzlichen Zeiger ganz leicht, 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:

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

    denen ich denke, dass ist das, was Sie nachher waren. Sie können tatsächlich tun dies, da sobald Sie geladen haben, bis first in die Zeiger Durchlaufen der Liste, die Sie wieder verwenden können first.

    InformationsquelleAutor der Antwort paxdiablo

  3. 27
    #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;
}

    InformationsquelleAutor der Antwort splicer

  4. 14

    Hier ist der code reverse eine einfach verknüpfte Liste in C.

    Und hier ist es klebte unten:

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

    InformationsquelleAutor der Antwort ma11hew28

  5. 4

    Ja. Ich bin sicher, Sie können tun dies in der gleichen Weise Sie können tauschen Sie zwei zahlen ohne die Verwendung einer Dritten. Einfach werfen die Zeiger auf ein int/long und ausführen der XOR-operation ein paar mal. Dies ist eine von den C-tricks, das macht für eine lustige Frage, aber keinen praktischen Wert.

    Können Sie reduzieren die O(n) Komplexität? Nein, nicht wirklich. Verwenden Sie einfach eine doppelt verkettete Liste, wenn Sie denken, Sie gehen zu müssen umgekehrter Reihenfolge.

    InformationsquelleAutor der Antwort brianegge

  6. 4

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

    Im Fall, dass nicht eine zyklische Liste ,daher NULL ist 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;
}

    InformationsquelleAutor der Antwort limitcracker

  7. 4

    Nur zum Spaß (obwohl tail-Rekursion Optimierung sollten aufhören, es zu Essen alle stack):

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

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

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

root = reverse(root, NULL);

    InformationsquelleAutor der Antwort Andrew Johnson

  8. 4

    Vertauschen der beiden Variablen ohne den Einsatz einer temporären variable,

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

    Schnellste Weg ist, es zu schreiben, in eine Zeile

    a = a ^ b ^ (b=a)

    Ähnlich,

    Verwendung von 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)

    Die gleiche Logik verwendet, um reverse-eine verlinkte Liste.

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

    InformationsquelleAutor der Antwort Sibi Rajasekaran

  9. 4

    Benötigen Sie eine track Zeiger die track-Liste.

    Müssen Sie zwei Zeiger :

    ersten Zeiger Holen ersten Knoten.
    zweite Zeiger zu Holen zweiten Knoten.

    Verarbeitung :

    Verschieben Track Zeiger

    Punkt zweiten Knoten zu dem ersten Knoten

    Bewegen Erste Zeiger, der einen Schritt durch die Zuordnung zweiten Zeiger zu einem

    Verschieben Zweite Zeiger um einen Schritt, Durch die Zuordnung von Track Zeiger auf zweite

    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;

    }

    InformationsquelleAutor der Antwort Sumit Arora

  10. 3

    Wie über die mehr lesbar:

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

    InformationsquelleAutor der Antwort Andrew Johnson

  11. 3

    Hier ist eine einfachere version in Java. Es hat nur zwei Zeiger 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
}

    InformationsquelleAutor der Antwort ernesto

  12. 2

    Ich verstehe nicht, warum es zurückgeben müssen Kopf, als wir übergeben es als argument. Wir passieren den Kopf des link-Liste, dann können wir auch update. Unten ist die 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;
}

    InformationsquelleAutor der Antwort Hardik Chauhan

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

    InformationsquelleAutor der Antwort Shridhar Gadade

  14. 0

    Arbeiten aus der Zeit-Komplexität des Algorithmus, die Sie verwenden jetzt und es sollte klar sein, dass es nicht verbessert werden kann.

    InformationsquelleAutor der Antwort John La Rooy

  15. 0

    Nein, nichts schneller als das aktuelle O(n) erledigt werden kann. Sie müssen sich verändern jeder Knoten, so wird die Zeit proportional zu der Anzahl der Elemente sowieso und das ist O(n), die Sie bereits haben.

    InformationsquelleAutor der Antwort sharptooth

  16. 0

    Mithilfe von zwei Zeigern, während die Aufrechterhaltung der Zeit-Komplexität von O(n), der am schnellsten erreichbar ist, kann nur möglich sein durch die Anzahl Typumwandlung von Zeigern und tauschen Ihre Werte. 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);
}

    InformationsquelleAutor der Antwort Apshir

  17. 0

    Ich habe einen etwas anderen Ansatz. Ich wollte mit den vorhandenen Funktionen (wie insert_at(index), delete_from(index)) zum umkehren der Liste (so etwas wie ein rechts-shift-operation). Die Komplexität ist immer noch O(n), aber der Vorteil ist mehr code wiederverwendet. Haben Sie einen Blick auf another_reverse () - Methode, 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;
}

    InformationsquelleAutor der Antwort FunBoy

  18. 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 ....

}

}

    InformationsquelleAutor der Antwort Amit Puri

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

    InformationsquelleAutor der Antwort Mr. Amit Kumar

  20. 0

    Ja, es ist ein Weg, mit nur zwei Zeigern. Das ist durch die Schaffung neuer Link-Liste, wo der erste Knoten ist der erste Knoten, der die Liste gegeben und der zweite Knoten der ersten Liste Hinzugefügt, um den start in die neue Liste und so weiter.

    InformationsquelleAutor der Antwort deepak verma

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

    InformationsquelleAutor der Antwort cpp

  22. 0

    Ich bin mit java zu implementieren und diese Herangehensweise ist test driven development daher Testfälle sind ebenfalls beigefügt.

    Die Knoten-Klasse, stellen einzelne Knoten -

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

    Service-Klasse, die dauert in der start-Knoten als Eingangs-und behalten, ohne zusätzlichen Platz.

    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 Den test-Fall deckt, dass das oben beschriebene Szenario. Bitte beachten Sie, dass Sie benötigen, junit Gläser. Ich bin mit testng.jar; Sie können jede was dir 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();
        }


    }
}

    InformationsquelleAutor der Antwort Mohammad Adnan

  23. 0

    Einen einfachen Algorithmus, wenn Sie die verknüpfte Liste als stack-Struktur:

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

}

    Kann die Leistung beeinträchtigt werden, da zusätzliche Funktion Aufruf der add und malloc, so dass die algorithmen der Adresse swaps sind besser, aber, dass man eigentlich erstellt neue Liste, so können Sie zusätzliche Optionen wie Sortieren oder entfernen von Elementen, wenn Sie fügen Sie eine callback-Funktion als parameter auf der Rückseite.

    InformationsquelleAutor der Antwort Ilian Zapryanov

  24. 0

    Hier ist ein bisschen anders, 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

    InformationsquelleAutor der Antwort Carl

  25. 0

    Folgenden wird eine Implementierung mit 2 Zeigern (Brust 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;
}

    InformationsquelleAutor der Antwort ARC

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

    InformationsquelleAutor der Antwort waqar ahmed

  27. 0

    Können Sie haben eine Lösung für dieses problem mit Hilfe von nur einem zusätzlichen Zeiger, dass zu statisch für die reverse-Funktion. 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;
    }
}

    InformationsquelleAutor der Antwort Shailendra Shrivastav

  28. 0

    Als alternative, können Sie mit Rekursion-

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

    InformationsquelleAutor der Antwort vaibhav

  29. 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

    InformationsquelleAutor der Antwort Jostein Topland

  30. -1

    Lösung mit 1 variable (Nur 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;

    InformationsquelleAutor der Antwort Vadakkumpadath

Schreibe einen Kommentar