Pairwise Swap von Knoten ohne Daten in LinkedList zu vertauschen

Question

Ich habe versucht, paarweise Swap von Linkedlist-Elementen zu tun. Anstelle der Elemente von Daten tauschen, ich tauschen sie durch die Links tauschen:

Eingang 1: 1->2->3->4->5 Ausgang 1: 2->1->4->3->5

Eingang 2: 1->2->3->4->5->6 Ausgang 2: 2->1->4->3->6->5

#include <iostream> 
using namespace std; 

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

struct node* func(struct node *f, struct node *s){ 
    if(s==NULL){ 
     return f; 
    } 

    struct node *rest1; 
    rest1 = s->next; 

    s->next = f; 
    if(rest1){ 
     f->next = func(rest1,rest1->next); 
    } 

    return s; 
} 

void show(struct node *head){ 
    while(head!=NULL){ 
     cout<<" "<<head->data; 
     head = head->next; 
    } 
} 

int main() { 
    //code 
    struct node *head =(struct node*)malloc(sizeof(struct node)); 
    head->data=1; 
    head->next = (struct node*)malloc(sizeof(struct node)); 

    head->next->data = 2; 
    head->next->next = (struct node*)malloc(sizeof(struct node)); 

    head->next->next->data = 3; 
    head->next->next->next = (struct node*)malloc(sizeof(struct node)); 

    head->next->next->next->data = 4; 
    //head->next->next->next->next=(struct node*)malloc(sizeof(struct node)); 
    //head->next->next->next->next->data=5; 

    head = func(head,head->next); 
    show(head); 
    return 0; 
} 

Dieser Code funktioniert gut für die Liste der ungeraden Länge, funktioniert aber nicht für die gerade Länge. Ich denke, das Problem ist in:

if(s==NULL){ 
    return f; 
} 

Aussage, die ich mache verwende zur vorherigen f->next=NULL (bei gleicher Länge).

Answer 1

Betrachten wir den Fall von gleicher Länge Liste sagen 1-> 2-> 3-> 4-> 5-> 6, wenn f Punkte auf 5, s Punkte auf 6 & REST1 Punkte auf NULL.

s-> next = f macht Knoten 6-> 5, aber Knoten 5 zeigt immer noch auf 6. Somit wird eine Schleife gebildet, wo 6-> 5-> 6-> 5 ........ ......bald.

So dieser Code Arbeit machen eine else-Anweisung hinzufügen hier

if(rest1){ 
     f->next = func(rest1,rest1->next); 
} 
else f->next = NULL; 

Dies wird 5- machen> NULL verhindert eine unendliche loop.Thus Ihre Funktion wie diese

struct node* func(struct node *f, struct node *s){ 
    if(s==NULL){ 
     return f; 
    } 

    struct node *rest1; 
    rest1 = s->next; 

    s->next = f; 
    if(rest1){ 
     f->next = func(rest1,rest1->next); 
    } 
    else f->next = NULL; 
    return s; 
} 

Answer 2

Da Sie dies als C++ markiert haben, würde ich STL <list> empfehlen. Sie können erreichen, was Sie wollen mit seiner splice Methode, mit der Sie die Liste bearbeiten können. Eine mögliche Implementierung würde in etwa so aussehen:

void alternate(list<int>& l) 
{ 
    if (l.empty()) 
     return; 
    auto from_itr = cbegin(l); 
    auto to_itr = from_itr; 
    for (; ++to_itr != cend(l) && ++to_itr != cend(l);) { 
     l.splice(to_itr, l, from_itr); 
     ++from_itr; 
    } 
} 

HINWEIS: Die from_itr in der Schleife erhöht wird, nur einmal, weil sie in der Liste verschoben wurden, um den nächsten Knoten von Interesse vorausgehen.