將鏈接列表轉換爲排序列表

Question

如何在插入新項目時將此列表轉換爲訂單列表？我有一個想法從哪裏開始，但一小部分的難題缺失。

這裏是我的代碼：

void Node:: insert(int dat) 
{ 
    Node * newnode = new Node(); 
    newnode->data=dat; 
    newnode->next=NULL; 
    if(first==NULL) 
    { 
     first=newnode; 
    } 
    else 
    { 
     Node *temp=first; 
     while(temp->next!=NULL) 
     { temp=temp->next; } 
     temp->next=newnode; 
    } 
} 

Answer 1

請嘗試以下

void Node:: insert(int dat) 
{ 
    Node *prev = NULL; 
    Node *current = first; 

    while (current != NULL && !(dat < current->data)) 
    { 
     prev = current; 
     current = current->next; 
    } 

    Node *newnode = new Node { dat, current }; 

    if (prev != NULL) prev->next = newnode; 
    else first = newnode; 
} 

我想，節點被定義爲

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

聲明

Node *newnode = new Node { dat, current }; 

你可以取代

Node *newnode = new Node(); 
newnode->data = dat; 
newnode->next = current; 

而且似乎等級節點的定義不正確，如果first是它的數據成員。

下面是一個簡化示例，演示了該功能的實際應用。當然，這是不是一個完整的例子

#include <iostream> 

class List 
{ 
public: 
    List() : first(NULL) {} 
    void insert(int dat) 
    { 
     Node *prev = NULL; 
     Node *current = first; 

     while (current != NULL && !(dat < current->data)) 
     { 
      prev = current; 
      current = current->next; 
     } 

     Node *newnode = new Node { dat, current }; 

     if (prev != NULL) prev->next = newnode; 
     else first = newnode; 
    } 

    void display() const 
    { 
     for (Node *current = first; current != NULL; current = current->next) 
     { 
      std::cout << current->data << ' '; 
     } 
    } 
private: 
    struct Node 
    { 
     int data; 
     Node *next; 
    } *first; 
}; 

int main() 
{ 
    List l; 

    l.insert(5); 
    l.insert(2); 
    l.insert(7); 
    l.insert(8); 
    l.insert(1); 
    l.insert(0); 
    l.insert(4); 
    l.insert(6); 
    l.insert(9); 
    l.insert(3); 

    l.display(); 
    std::cout << std::endl; 

    return 0; 
} 

輸出是

0 1 2 3 4 5 6 7 8 9