順序單鏈表歸併排序-騰訊筆試題
對單鏈表進行歸併排序,單鏈表與數組相比只能順序訪問每個元素,因此在使用二路歸併排序時關鍵在於找到鏈表的中間結點將鏈表一分爲二:可以利用一個步長爲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);
-
寧夏臨牀醫師資格綜合筆試考試科目
寧夏臨牀醫師資格綜合筆試考試科目已經公佈,具體安排如下:日期時間考試科目9月12日(星期六)上午9:00—11:30第一單元下午14:00—16:30第二單元9月13日(星期日)上午9:00—11:30第三單元下午14:00—16:30第四單元考前一天準備和考中注意事項:1、重點複習公共科目和基礎科目。內...
-
騰訊實習生筆試拾遺
知識橫向要求:(1)由於職位是視覺設計,互聯網UI方面,題目出現了groupon、twitter、facebook、豆瓣、QQ空間、QQ校友、AIM這些互聯網產品,這要求對互聯網方面有較多涉獵。(2)填空題還是問到常用的視頻編輯軟件,iOS,網頁分辨率與印刷產品分辨率分別是多少。(3)選擇題有...
-
時代地產筆試經驗
篇一時代地產,我自十月開始投簡歷以來,第一家給我筆試機會的公司,本來還挺興奮,來到筆試現場,才發現,這家公司挑選簡歷的門檻並不高。簡單說下:時間120分鐘,據監考人員自己稱,題量很大,語數外涵蓋,大家要抓緊時間!另:兩位監考mm,一位長直髮,一位捲髮束成馬尾狀,都年輕的緊,看到...
-
雲南省文山州住房公積金管理中心筆試相關說明
准考證領取時間:3月10日上午8:00-11:30,下午2:30-17:30。准考證領取地點:文山市果園街35號,原文山州就業局3樓(報名地點領取)。筆試時間:3月11日上午9:00-11:30。筆試地點:文山市第一初級中學北校區(12路公交車)。特別說明:1、本次考試將統一配備考試文具,考生無需自帶考試...