在C++的鏈表中分離偶數和奇數節點

所以，我自學數據結構和算法。在解決一些問題時，我遇到了下面的問題，我必須分離鏈表的奇偶節點。在C++的鏈表中分離偶數和奇數節點

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

它看起來直截了當和我以爲只是通過刪除節點和調整幾個指針可以解決這個問題，要解決這一點，但它不是情況

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

所以當我執行上面的代碼我得到

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

現在，我想我失去了一些東西，而d選擇節點。不知道我在這裏做錯了什麼。我認爲我沒有正確照顧指針調整。我非常感謝這裏的任何幫助。

感謝，

來源

2016-12-09 kkard

當你刪除第一個節點時，你不更新'main'中的'head'。它始終指向節點1. 還有一個稍微複雜一點的算法，如果您想要挑戰，可以讓它在適當的位置進行。 – Donnie

查看鏈接列表的[* head sentinel * trick]（http://www.brpreiss.com/books/opus5/html/page97.html），在頭部之前維護一個額外的節點（無負載）更簡單的編碼（也見[見這裏]（https://en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons））。最後一個環節是關於在尾部增加名單;就像Lisp的[The Pitmanual的Sheep trick]一樣（http://www.maclisp.info/pitmanual/funnies.html）。 –

如果你不想創建第二個列表，這是不是真的有必要，你能做的最好的事情是這樣的算法：

1）找到的最後一個元素（你可以在線性時間內做到這一點）

2）開始遍歷列表，每次你找到一個奇怪的元素，你把它放在列表的末尾。很容易，你只需要調整前面元素的指針，後面的元素，奇怪的元素本身和最後一個元素。

執行＃2，直到找不到列表的最後一個元素。爲了跟蹤這個，你必須爲最後一個元素保存兩個指針，當你在最後一個元素中放置奇數元素時你將更新這個指針，而另一個只會標記原始列表的結束，允許你終止算法。

來源

2016-12-09 23:49:52 bracco23

在C++的鏈表中分離偶數和奇數節點

回答

相關問題