兩路歸并排序（升序排列） ?(平均/最差)時間復雜度O(NlogN)

將兩個有序的單鏈表合并為一個有序的單鏈表，默認是按升序排列的。

合并操作是非常適合用遞歸來完成的一類操作，遞歸實現將會比迭代實現更加清晰且易于理解。
盡管如此，你可能也不愿意使用遞歸來實現這個操作，因為遞歸方法所使用的棧空間與鏈表的長度成正比。

部分關鍵代碼如下：

typedef struct _Node_t {struct _Node_t *next;int data; }Node;Node *Merge(Node *head1, Node *head2)//時間復雜度：O(nlogn) {Node *head = NULL;if (NULL == head1){return head2;}if (NULL == head2){return head1;}while ((NULL != head1) && (NULL != head2)){if (head1->data < head2->data){head = head1;head->next = Merge(head1->next, head2);}else{head = head2;head->next = Merge(head1, head2->next); }}return head; }

總結

以上是生活随笔為你收集整理的两路归并排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。