順序單鏈表歸併排序-騰訊筆試題
對單鏈表進行歸併排序,單鏈表與數組相比只能順序訪問每個元素,因此在使用二路歸併排序時關鍵在於找到鏈表的中間結點將鏈表一分為二:可以利用一個步長為2的指針和一個步長為1的指針同時遍歷單鏈表,當步長為2的`指針指向鏈表最後一個結點或者最後一個結點的下一個結點時,步長為1的指針即指向鏈表的中間結點。然後是兩個有序單鏈表的合併問題。時間複雜度為O(N*logN),空間複雜度為O(1)。
//mergesort for LinkList
#include
#include
#include
using namespace std;
typedef struct Node {
int data;
struct Node* next;
} LNode, *LinkList;
Node* getMiddle(LinkList L) {//無頭結點鏈表
LNode *mid, *midl, *p;
midl = NULL, p = mid = L;
while (p != NULL && p->next != NULL) {//利用快慢指針找鏈表的中間位置並將鏈表1分為2
p = p->next->next;
midl = mid;
mid = mid->next;
}
midl->next = NULL;//將鏈表1分2
return mid;
}
void printList(LinkList L) {
LNode *p;
p = L;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;;
}
void Merge(LinkList &La, LinkList Lb) {//將兩個有序鏈表La和Lb合併成一個有序鏈表La
LNode *pa = La, *pb = Lb;
LinkList Lc = NULL;
LNode *q = NULL;
if (pa->data <= pb->data) {
Lc = q = pa;
pa = pa->next;
}
else {
Lc = q = pb;
pb = pb->next;
}
while (pa != NULL && pb != NULL) {
if (pa->data <= pb->data) {
q->next = pa, pa = pa->next, q = q->next;
}
else {
q->next = pb, pb = pb->next, q = q->next;
}
}
if (pa == NULL) q->next = pb;
else if (pb == NULL) q->next = pa;
La = Lc;//La重新指向合併後的鏈表
}
void MergeSort(LinkList &L) {//注意引用的使用
if (L == NULL || L->next == NULL) return;//當鏈表長度小於等於1時即不用再分
LinkList La, Lb;
Lb = getMiddle(L);
La = L;
MergeSort(La);
MergeSort(Lb);
Merge(La, Lb);
L = La;//返回的結果代回
}
void DestroyList(LinkList &L) {
LNode *p, *q;
p = q = L;
while (p != NULL) {
q = q->next;
free(p);
p = q;
}
}
int main() {
int len = 10, i;
LinkList L;
LNode *p;
if ((L = (LinkList)malloc(sizeof(LNode))) == NULL) {
cerr << "Error in allocate memory!" << endl;
return -1;
}
srand(time(NULL));
L->data = rand() mod 1000; L->next = NULL;
for (i = 1; i < len; i++) {
if ((p = (LNode*)malloc(sizeof(LNode))) == NULL) {
cerr << "Error in allocate memory!" << endl;
DestroyList(L);
return -1;
}
p->data = rand() mod 1000;
p->next = L->next;
L->next = p;//頭插
}
cout << "The list before sorting:" << endl;
printList(L);
MergeSort(L);
cout << "The list after sorting:" << endl;
printList(L);
DestroyList(L);
相關文章
-
騰訊的一道鏈表筆試題「總結」
相傳:奧拉和賽爾在宇宙中生活得很和諧,但是有一天突然宇宙中出現一個洛克星球,上面有着黑衣人和寵物,剛開始洛克星球沒什麼動靜可是有一天賽爾號飛船想上這個星球觀察觀察,可是賽爾號的飛船快到這個星球上時看見洛克星球上 -
會計學專業課程修讀順序,幫忙排個順序
如題,會計學專業課程修讀順序,幫忙排個順序 -
騰訊公司招聘c/c++程序員筆試題1
騰訊公司招聘c/c++程序員筆試題騰訊公司c/c++筆試題這部分的騰訊c/c++面試用的筆試題主要是c/c++、數據結構、簡單算法、操作系統等方面的基礎知識,方便去騰訊面試開發的同仁有所參考!筆試題的題型好像有sizeof、樹等 -
國小生句子排列順序練習題
句子排列是國小語文中一個很重要的能力,通過句子的排序,增強對語文的感知和認知,提升語文的理解和辨析能力,下面是小編為大家分享的國小生句子排列順序練習題,我們一起來看看吧! 國小生句子排列順序練習題 1.把下列幾 -
對百度、騰訊、阿里巴巴三家公司進行排序
未來50年以後只有一家公司還是龍頭,你覺得會是哪一家以及原因?這是面試時遇到的問題,感覺自己答得不是很精確,有沒有大神願意發表一下自己看法。多謝 -
程序員面試題之兩鏈表的第一個公共結點[數據結構]
題目:兩個單向鏈表,找出它們的第一個公共結點。鏈表的結點定義為:struct ListNode{int m_nKey;ListNode* m_pNext;};分析:這是一道微軟的面試題。微軟非常喜歡與鏈表相關的題目,因此在微軟的面試題中,鏈表出現的概率相當高 -
關於理綜考試做題順序和答題思路
關於答題理綜考試是理科考生學習水平的綜合體現,對理科生來説是重點也是難點。考生要在做題時講究策略和技巧,不然很難把水平發揮到極致。做題速度:穩中求快準確第一提示:理綜第Ⅰ卷答題不要超70分鐘一般而言,理綜科第Ⅰ卷 -
傳統志願(順序志願)的投檔順序是怎樣的
歷史 是一條時間的長河 沒有上游的蜿蜒 就沒有下游的風光 沒有八年戰士浴血的抗戰 就沒有今日光復的台灣 沒有遷台的數百萬萬兩黃金 成全不了台灣今日的光輝 兩岸分治 從軍事的抗衡 -
騰訊程序員1年寫多少代碼?
騰訊程序員1年寫多少代碼?性別及年齡散佈介紹行業內,騰訊員工的薪資待遇和福利應當是比較好的,很多IT程序員都想進入到騰訊工作,近日,騰訊大講堂發起了1個很有興趣的`話題:“騰訊程序員1年寫多少代碼”,答案是3億行?有無嚇哭 -
《歸去來兮辭並序》優秀教學實錄
【教學目標】1.掌握重要實詞、虛詞、古今異義詞、詞類活用、特殊句式等文言知識。2.在瞭解文章大意的基礎上體味作者複雜的思想感情。 【教學重難點】1.學習重點:落實具體的文言知識及涵詠體味文章的思想感情。2.學