試圖使用合併函數對鏈表進行排序？

我寫了一個函數來合併兩個單獨鏈接的列表。例如，如果A = 1 2 3和B = 3 4 5和我合併它們兩者，我得到A = 1 2 3 3 4 5和B = NULL。我現在想要做的是編寫一個函數，使用mergesort算法對單個鏈表進行排序（以某種方式使用我的合併函數）。對於mergesort，如果我沒有錯，我將不得不以某種方式將鏈表分成兩半，然後完成剩下的工作。我有一個小綱要，寫下我想如何去做。我不確定我現在該怎麼做分裂。任何幫助表示讚賞！試圖使用合併函數對鏈表進行排序？

  List mergeSort(List L) { 
      if(|L| > 1) { 
       split L into L1 and L2; 
       L1 = mergeSort(L1); 
       L2 = mergeSort(L1); 
       return(merge(L1,L2)); 
      } 
      }

我的合併以下功能：

void mylist::merge(mylist& b) 
{ 
    if (!this->isSorted() || !b.isSorted()) 
     cout << "error" << endl; 
    Node* ptr1 = b.head; 
    Node* prev_a = NULL; 
    Node* curr_a = head; 
    Node* curr_b = ptr1; 
    while (curr_b) { 
     if (curr_a && head->key < ptr1->key) { 
      prev_a=curr_a; 
      curr_a = curr_a->next; 
     } 
     else { 
      Node* b_next = curr_b->next; 
      curr_b->next = curr_a; 
      if (prev_a) prev_a->next = curr_b; 
      else head = curr_b; // curr_b is first element in 'a' 
       prev_a = curr_b; 
      curr_b = b_next; 
     } 
    return; 
}

來源

2014-10-29 sparta93

實現，問題是平凡的，如果兩個列表有自下而上歸併的1 – 2014-10-29 03:14:05

聽說過的長度是多少？鏈接列表很好用 – smac89 2014-10-29 03:14:12

@ Smac89不是真的，我會如何實現這一點？ – sparta93 2014-10-29 03:20:05

爲了將列表分爲兩半，可以使用兩個指針。

兩個指針都從列表頭開始。一個指針每兩步移動一次，而另一個指針每移動一步。當快速指針變爲空時，較慢的指針將指向列表中間。

ListNode *fast(head->next), *slow(head); while(fast && fast->next) { fast = fast->next->next; slow = slow->next; }

來源

2014-10-29 05:37:43 ljshou

試圖使用合併函數對鏈表進行排序？

回答

相關問題