排序鏈接列表C++與指針

Question

我一直在掙扎幾個小時，結束了這個問題。我的目標是僅使用指針對鏈表進行排序（我不能將鏈表放入vec或數組中，然後進行排序）。我得到了指向列表頭節點的指針。我可以調用指針的唯一方法是head-> next（next node）和head-> key（存儲在節點中的int值，用於比較）。我一直在過度使用我的白板，並嘗試幾乎所有我能想到的東西。

Node* sort_list(Node* head) 
{ 
    Node* tempNode = NULL; 
    Node* tempHead = head; 
    Node* tempNext = head->next; 

    while(tempNext!=NULL) { 

     if(tempHead->key > tempNext->key) { 
      tempNode = tempHead; 
      tempHead = tempNext; 
      tempNode->next = tempNode->next->next; 
      tempHead->next = tempNode; 
      tempNext = tempHead->next; 
      print_list(tempHead); 


     } 
     else { 
      tempHead = tempHead->next; 
      tempNext = tempNext->next; 

     } 
    } 
    return head; 
} 

Answer 1

因爲它是一個單向鏈表，我們可以這樣做：（僞代碼）

bool unsorted = true; 
while(unsorted) { 
    unsorted = false; 
    cur = head;   

    while(cur != nullptr) { 
     next = cur->next; 
     if(next < cur) { 
      swap(cur, next) 
      unsorted = true; 
     } 

     cur = cur->next; 
    }  
} 

Answer 2

假定這樣的節點：

struct Node 
{ 
    Node *next; 
    int key; 
    Node(int x) : key(x), next(NULL) {} 
}; 

使用插入排序算法來排序列表：

Node* sort_list(Node* head) 
{ 
    Node dumy_node(0); 
    Node *cur_node = head; 

    while (cur_node) 
    { 
     Node *insert_cur_pos = dumy_node.next; 
     Node *insert_pre_pos = NULL; 

     while (insert_cur_pos) 
     { 
      if (insert_cur_pos->key > cur_node->key) 
       break; 

      insert_pre_pos = insert_cur_pos; 
      insert_cur_pos = insert_cur_pos->next; 
     } 

     if (!insert_pre_pos) 
      insert_pre_pos = &dumy_node; 

     Node *temp_node = cur_node->next; 

     cur_node->next = insert_pre_pos->next; 
     insert_pre_pos->next = cur_node; 

     cur_node = temp_node; 
    } 

    return dumy_node.next; 
} 

Answer 3

Don不會感覺不好，這比聽起來要困難得多。如果這是在一個數組中，它會相當容易。如果列表是雙重鏈接的，那將更容易。看看這個代碼，它實現了一個插入排序

struct Node { 
    int key; 
    Node *next; 
    } *NodePtr; 

// do a simple selection sort http://en.wikipedia.org/wiki/Selection_sort 
Node* sort_list(Node* head) { 
    Node *top = nullptr; // first Node we will return this value 
    Node *current = nullptr; 
    bool sorted = false; 
    while (sorted == false) { 
     // we are going to look for the lowest value in the list 
     Node *parent = head; 
     Node *lowparent = head; // we need this because list is only linked forward 
     Node *low = head; // this will end up with the lowest Node 
     sorted = true; 
     do { 
      // find the lowest valued key 
      Node* next = parent->next; 
      if (parent->key > next->key) { 
       lowparent = parent; 
       low = next; 
       sorted = false; 
       } 
      parent = parent->next; 
      } while (parent->next != nullptr); 
     if (current != nullptr) { // first time current == nullptr 
      current->next = low; 
      } 
     // remove the lowest item from the list and reconnect the list 
     // basically you are forming two lists, one with the sorted Nodes 
     // and one with the remaining unsorted Nodes 
     current = low; 
     if (current == head) { head = current->next; } 
     lowparent->next = low->next; 
     current->next = nullptr; 
     if (top == nullptr) { 
      top = current; 
      } 
     }; 
    current->next = head; 
    return top; 
    } 

int _tmain(int argc, _TCHAR* argv []) { 
    Node nodes[4]; 
    nodes[0].key = 3; 
    nodes[1].key = 4; 
    nodes[2].key = 5; 
    nodes[3].key = 1; 

    nodes[0].next = &nodes[1]; 
    nodes[1].next = &nodes[2]; 
    nodes[2].next = &nodes[3]; 
    nodes[3].next = nullptr; 

    auto sortedNodes = sort_list(&nodes[0]); 

    return 0; 
    } 

Answer 4

，因爲它是處理鏈接結構的最簡單的方法使用遞歸方法：

僞代碼：

SORT(head) 
if (head->next == null) 
    return 
tempNode = head->next 
SORT(tempNode) 
if (tempNode->value < head->value) 
    SWAP(head, tempNode) 
    SORT(head) 
return 

所以假設您有5 4 3 2 1

1）5 4 3 1 2

2）5 4 1 3 2

3）5 4 1 2 3

4）5 1 4 2 3

5）5 1 2 4 3

...

n）1 2 3 4 5

Answer 5

int swapNode(node * &first, node * &second) 
{ 
    //first we will declare the 
    //previous of the swaping nodes 
    node *firstprev=NULL; 
    node*secprev=NULL; 
    node*current=head; 
    //set previous first 
    while(current->next!=first) 
    { 
     current=current->next; 
    } 
    firstprev=current; 
    //seting 2nd previous 
    while(current->next!=second) 
    { 
     current=current->next; 
    } 

// swap datas, assuming the payload is an int: 
int tempdata = first->data; 
first->data = second->data; 
second->data = tempdata; 
//swaping next of the nodes 
firstprev->next=second; 
secprev->next=first; 
}