ペアワイズLinkedListのデータをスワップしないノードのスワップ

Question

私はlinkedlist要素のペアワイズスワップを実行しようとしています。

入力1：1->2->3->4->5 出力1：2->1->4->3->5

入力2：1->2->3->4->5->6 出力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; 
} 

データによって要素を交換する代わりに、私はリンクを交換することによって、それらを交換しています

このコードは奇数長のリストでは問題ありませんが、偶数の長さでは機能しません。 私は問題はであると思う：私は作るために使用しています

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

文の前のf->next=NULL（偶数長の場合）。

Answer 1

偶数長のリストの場合はをnullに1-> 2-> 3-> 4-> 5-> 6場合のF 5を指し、S点6つの & rest1点に言う検討します。 012-> next = fはノード6-> 5を作成しますが、ノード5は6を指します。したがって、6-> 5-> 6-> 5 ........のループが形成されます。 ......など。したがって、これは無限loop.Thusあなたの機能を妨げる5> NULLを行いますこのコードの動作がここ

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

をelseステートメントを追加作成する

この

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

これをC++とタグ付けしたので、STLの<list>をお勧めします。 spliceメソッドを使用すると、リストを操作することができます。

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

注：関心の次のノードの前にリストに移動されているので、ループ内from_itrだけ一度をインクリメントさ 1つの可能な実装は、次のようになります。