合併2個鏈接列表並追加到鏈接列表的末尾C++

Question

到目前爲止，我還沒有太多工作，但我正在嘗試使用鏈接列表。

結構：

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

我如何添加一個節點到列表的末尾？我只是試圖接受一個列表頭和一個int值的指針作爲新節點添加。當我嘗試運行我目前有的異常時。

void addNode(Node* head, int x) 
{ 

    Node* temp = new Node; 
    temp->data = x; 
    temp->next = NULL; 

    if(!head) 
    { 
     head = temp; 
     return; 
    } 
    else 
    { 
     Node* last = head; 
     while(last->next) 
     last=last->next; 

     last->next = temp; 
    } 
} 

我還沒有真正開始合併這兩個列表。我只知道我需要接收2個鏈表（或指向2個鏈表的頭部的指針？），然後遍歷所有節點的列表。

EG：鏈表1具有3個節點：4，10，20 鏈表2具有4個節點：2，5，15，60

合併列表功能將導致一個新的鏈接列表以2,4,5,10,15,20,60作爲節點。

編輯：在我的主，我打電話的ADDNODE功能，像這樣：

Node *head = new Node; 

insertAtEnd(head,20); 

那是正確的或會是異常的原因是什麼？

Answer 1

聲明功能通過以下方式和

void addNode(Node* &head, int x) ; 

，而不是這個代碼片斷

Node *head = new Node; 

insertAtEnd(head,20); 

你要調用的函數在第一時間通過以下方式

Node *head = nullptr; // or NULL 

addNode(head,20); 

公告在您的帖子中沒有名稱爲insertAtEnd的功能。有功能addNode。:)

如果你需要合併兩個列表，那麼你可以使用這個演示程序作爲示例。當然，您需要添加一些其他功能，例如刪除列表以獲得完整的項目。

#include <iostream> 

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

Node * insert(Node *current, int value) 
{ 
    Node *tmp; 

    if (current == nullptr) 
    { 
     tmp = new Node { value, nullptr }; 
    } 
    else 
    { 
     tmp = new Node { value, current->next }; 
     current->next = tmp; 
    } 

    return tmp; 
} 

std::ostream & display(Node *head, 
         std::ostream &os = std::cout, 
         const char *delimiter = " ") 
{ 
    for (; head; head = head->next) os << head->value << delimiter; 

    return os; 
} 

Node * merge(Node * &head1, Node * &head2) 
{ 
    Node *new_head = nullptr; 
    Node *current = nullptr; 

    while (head1 != nullptr && head2 != nullptr) 
    { 
     Node *tmp; 
     if (head2->value < head1->value) 
     { 
      tmp = head2; 
      head2 = head2->next; 
     } 
     else 
     { 
      tmp = head1; 
      head1 = head1->next; 
     } 

     tmp->next = nullptr; 
     if (new_head == nullptr) 
     { 
      new_head = tmp; 
      current = new_head; 
     } 
     else 
     { 
      current->next = tmp; 
      current = current->next; 
     } 
    } 

    if (head1 != nullptr) new_head == nullptr ? new_head : current->next = head1; 
    if (head2 != nullptr) new_head == nullptr ? new_head : current->next = head2; 


    head2 = nullptr; 
    head1 = new_head; 

    return new_head; 
} 

int main() 
{ 
    Node *list1 = nullptr; 
    Node *list2 = nullptr; 

    list1 = insert(list1, 4); 
    insert(insert(list1, 10), 20); 

    display(list1, std::cout << "List1: ") << std::endl; 

    list2 = insert(list2, 2); 
    insert(insert(insert(list2, 5), 15), 60); 

    display(list2, std::cout << "List2: ") << std::endl; 

    std::cout << std::endl; 

    merge(list1, list2); 

    display(list1, std::cout << "List1: ") << std::endl; 
    display(list2, std::cout << "List2: ") << std::endl; 

    return 0; 
} 

程序輸出是

List1: 4 10 20 
List2: 2 5 15 60 

List1: 2 4 5 10 15 20 60 
List2: 

Answer 2

這可能是例外的原因：

struct Node 
{ 
    int value;  <----- Node structure has value property 
    Node *next; 
}; 


Node* temp = new Node; 
temp->data = x; <------ Assigning to data property of Node which does not exists 
temp->next = NULL; 

要添加列表，你可以使用同樣的方法

void addNode(Node* head, Node* head2) 
{ 

    Node* last = head; 
    while(last->next) last=last->next; 

    last->next = head2; 
} 

Answer 3

這樣做這個：

void addNode(Node* head, int x) 
// here ---------^ 

再後來這樣的：

head = temp; // here 

你只需修改本地head指針，它把從調用者傳遞的地址值。由於head不是對指針的實際引用（它只是一個指針），結果是調用者的指針傳遞爲head保持不變。你永遠不會將你分配的節點追加到你的列表中，泄漏內存，這將成爲一個悲哀的日子......

而是通過引用傳遞指針。修復這一點，那麼固定無效data成員，它實際上應該是value和指針到指針走在列表中找到結束，其結果可能是這個樣子：

#include <iostream> 

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

void addNode(Node*& head, int x) 
{ 
    Node **pp = &head; 
    while (*pp) 
     pp = &(*pp)->next; 
    *pp = new Node; 
    (*pp)->value = x; 
    (*pp)->next = nullptr; 
} 

void printList(const Node *head) 
{ 
    for (; head; head = head->next) 
     std::cout << head->value << ' '; 
    std::cout << '\n'; 
} 

void freeList(Node *&head) 
{ 
    while (head) 
    { 
     Node *p = head; 
     head = p->next; 
     delete p; 
    } 
} 

int main() 
{ 
    Node *head = nullptr; 

    for (int i=1; i<=5; ++i) 
     addNode(head, i); 

    printList(head); 
    freeList(head); 
} 

輸出

1 2 3 4 5 

我離開了爲您實施實際合併的任務，但這應該足以讓您獲得可管理的列表並啓動並運行。

---

更新：從OP的編輯問題：

Node *head = new Node; 

insertAtEnd(head,20); 

除了現在已經是一個完全不同的命名功能，您的節點是默認初始化。在你的情況，這意味着從new Node;產生的Node具有爲都value和next不確定值。然後你將它傳遞給你的函數，該函數假定一個確定的值（null）來終止你的循環。

這可以通過多種方式修復;上面代碼的機制就是這樣一種方式。如果列表管理代碼理解爲NULL表示無列表，則不需要預先分配頭節點。您的addNode原始帖子似乎至少嘗試遵循該口頭禪。

Answer 4

編輯：在我的主，我打電話的ADDNODE功能，像這樣：

Node *head = new Node; 
insertAtEnd(head,20); 

這是不對的。您沒有初始化head->next，因此在insertAtEnd中，代碼while(last->next) last=last->next;將嘗試比較未初始化的指針，如果它不爲null，則將對其進行取消引用。這可能會導致程序崩潰，而不是拋出異常。然後再次，它是未定義的行爲，所以可能發生任何事情。

由於您插入功能已經涵蓋插入到空單的情況下，我會簡單地調用

head = nullptr; 
insertAtEnd(head,20)`; 

除此之外，還有永不更新的功能外head指針，它已經被覆蓋的bug在其他答案。