C++のリンクリストに偶数ノードと奇数ノードを分離する

Question

したがって、私は自己教授データ構造とアルゴリズムです。いくつかの問題を解決しながら、私はリンクされたリストの奇数と偶数のノードを分離しなければならない問題に遭遇しました。

http://www.geeksforgeeks.org/segregate-even-and-odd-elements-in-a-linked-list/

、次のような問題文です：整数のリンク一覧を考える

、すべての偶数番号が変更されたリンクリストにあるすべての奇数番号の前に現れるように、リンクされたリストを変更するための関数を書きます。また、偶数と奇数の順序は同じにしてください。

私はこの質問が何度も尋ねられることを知っています。しかし、私はまだ答えを見つけることができません。私はちょうどノードを削除し、いくつかのポインタを調整することによって、問題を解決するだろうと思ったが、それはないです。この問題を解決するために、複数の方法があります知っているが、道

1. Traversing over the original list and moving all the odd elements to new oddlist. 
     Same time delete those elements from the original list. 
    2. Now original list should have even elements and oddlist will have odd elements. 
    3. concatenate original list and oddlist 

まっすぐ前方に見える

と を以下でこれを解決しようとします私は今

1 8 4 5 1 5 instead of 2 8 4 1 5 7 

を取得しています上記のコードを実行するとき場合

#include <iostream> 
#include <stdlib.h> 

using namespace std; 

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


struct Node *Insert_at_bottom(struct Node* head, int data) { 
    struct Node *node; 

    node = new struct Node; 
    node->data = data; 
    node->next = NULL; 
    //node->prev = NULL; 

    struct Node *temp; 

    if (head == NULL) { 
     head = node; 
     return head; 
    } 

    temp = head; 
    while(temp->next != NULL){ 
     temp = temp->next; 
    } 

    temp->next = node; 
    //node->prev = temp; 
    return head; 
} 




struct Node *seperate_elements(struct Node *head) { 
    struct Node *temp = head; 
    struct Node *oddhead = NULL; 
    struct Node *temp1 = NULL; 
    while (temp != NULL) { 
     if (temp->data%2 == 0) { 
      cout << "even:" << temp->data << "\n"; 


     } 
     else{ 
      cout << "odd:" << temp->data << "\n"; 
      oddhead = Insert_at_bottom(oddhead, temp->data); 

      // I am messing something here. Not sure what!!! 
      temp1 = temp->next; 
      temp->next = temp1->next; 
      //temp->next = temp->next->next; 
      free(temp1); 
     } 

     temp = temp->next; 
    } 
    return oddhead; 
} 

struct Node *concate_list(struct Node *head, struct Node *oddhead) { 
    struct Node *temp = head; 
    while(head->next!=NULL) 
    { 
     head = head->next; 
    } 
    head->next = oddhead; 
    return temp; 

} 

void print_list(struct Node *head){ 
    while(head){ 
     cout << head->data << " "; 
     head = head->next; 
    } 
} 

int main(){ 

    struct Node *head = NULL; 
    struct Node *head2 = NULL; 
    struct Node *finalhead = NULL; 
    head = Insert_at_bottom(head, 1); 
    head = Insert_at_bottom(head, 2); 
    head = Insert_at_bottom(head, 8); 
    head = Insert_at_bottom(head, 4); 
    head = Insert_at_bottom(head, 5); 
    head = Insert_at_bottom(head, 7); 

    head2 = seperate_elements(head); 


    finalhead = concate_list(head, head2); 
    //cout << "\n"; 
    print_list(finalhead); 

    return 0; 
} 

ので、私はDながら、私は何かが足りないと思いますノードを選ぶ。私がここで間違っていることを確かめない。私はポインタ調整の適切な世話をしていないと思う。私は本当にここで何か助けていただければ幸いです。

1）最後の要素を見つける：あなたが本当に必要ではない第二のリストを作成したくない場合は、あなたができる最善のことは、このようなアルゴリズムである

Answer 1

おかげで、 （あなたは線形時間でそれを行うことができます）

2）リストを横断し始めると、奇妙な要素が見つかるたびにリストの最後に置きます。簡単ですが、前の要素、次の要素、奇数要素自体、最後の要素のポインタを調整するだけです。

リストの最後の要素が見つからなくなるまで＃2を実行します。これを追跡するには、最後の要素の2つのポインタを保存する必要があります.1つは最後の要素に奇数要素を入れて更新し、もう1つは元のリストの最後をマークします。アルゴリズム。