思路：

1.將鏈表的中點(diǎn)找到，對(duì)其切分成2條

2.繼續(xù)步驟1，切成4條，8條。。。,直至每段鏈表只有1個(gè)元素

3.歸并操作，對(duì)兩兩鏈表進(jìn)行合并排序，并返回回并后的鏈表的頭結(jié)點(diǎn)，依次向上遞歸回去

C++代碼實(shí)現(xiàn)

鏈表頭文件鏈接：https://github.com/hitskyer/course/tree/master/dataAlgorithm/chenmingming/linkedList/homework

//歸并排序 // Created by mingm on 2019/3/23. // #include <iostream> #include <time.h> #include <cstdlib> #include "./homework/singleList.cpp" using namespace std;ListNode GetMidNode(ListNode s) //快慢指針?lè)?獲取中間節(jié)點(diǎn) {ListNode fast, slow;fast = s->pNext;//讓快指針早點(diǎn)到達(dá)末位，慢指針指向中點(diǎn)或者(偶數(shù)個(gè)長(zhǎng)度時(shí))中點(diǎn)前一個(gè)位置slow = s;while(fast && fast->pNext){fast = fast->pNext->pNext;slow = slow->pNext;}return slow; } ListNode mergeList(ListNode L, ListNode R) //歸并函數(shù) {if(L == NULL) //如果一邊為空，則返回另一邊的頭結(jié)點(diǎn)return R;if(R == NULL)return L;ListNode tempL = L, tempR = R; //把左右表頭存儲(chǔ)起來(lái)ListNode temp = new SNode, emptyHead = temp; //利用一個(gè)空表頭哨兵tempwhile(tempL && tempR) //左右鏈表均不為空的話，進(jìn)行數(shù)據(jù)比較{if(tempL->data < tempR->data){temp->pNext = tempL;temp = temp->pNext;tempL = tempL->pNext;}else{temp->pNext = tempR;temp = temp->pNext;tempR = tempR->pNext;}}if(tempL) //如果左邊還有剩余的節(jié)點(diǎn)，把其接入鏈表末尾temp->pNext = tempL;if(tempR) //如果右邊還有剩余的節(jié)點(diǎn)，把其接入鏈表末尾temp->pNext = tempR;temp = emptyHead->pNext; //實(shí)際鏈表數(shù)據(jù)節(jié)點(diǎn)表頭delete emptyHead; //釋放new出來(lái)的哨兵emptyHead = NULL;return temp; //返回鏈表數(shù)據(jù)頭結(jié)點(diǎn) } ListNode divList(ListNode Lhead) {if(Lhead == NULL || Lhead->pNext == NULL) //鏈表長(zhǎng)度為0或者1，不用排序return Lhead;ListNode Mid = GetMidNode(Lhead); //獲取鏈表中間節(jié)點(diǎn)(如果長(zhǎng)度為2，則Mid是第一個(gè)節(jié)點(diǎn))ListNode Rhead = Mid->pNext; //右邊鏈表表頭地址Mid->pNext = NULL; //斷開(kāi)左右鏈表ListNode L = divList(Lhead); //繼續(xù)對(duì)左右兩條鏈表進(jìn)行劃分ListNode R = divList(Rhead);return mergeList(L,R); //返回merge后的鏈表的表頭 } ListNode mergeSort(ListNode head) //歸并排序入口，將頭結(jié)點(diǎn)地址傳入 {if(head == NULL || head->pNext == NULL) //鏈表長(zhǎng)度為0或者1，不用排序return head;elsedivList(head); //長(zhǎng)度大于1，則對(duì)其進(jìn)行劃分將鏈表切片 }int main() {srand((unsigned)time(NULL)); //用時(shí)間隨機(jī)數(shù)種子size_t len = 10; //測(cè)試鏈表最大長(zhǎng)度f(wàn)or(size_t j = 0; j < len; ++j){SingleList intList;for(size_t i = 0; i < j; ++i){intList.AddTail(rand()%100); //添加隨機(jī)數(shù)到鏈表}cout << "before merge sort: " << endl;intList.PrintList(); //排序前鏈表打印intList.SetHeadNode(mergeSort(intList.GetHeadNode())); //把排序后的鏈表的頭結(jié)點(diǎn)設(shè)置成鏈表的頭結(jié)點(diǎn)cout << "after merge sort: " << endl;intList.PrintList(); //排序后鏈表打印}return 0; }

Valgrind檢查結(jié)果

總結(jié)

以上是生活随笔為你收集整理的数据结构--链表--单链表归并排序mergesort的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。