顺序单链表归并排序-腾讯笔试题
对单链表进行归并排序,单链表与数组相比只能顺序访问每个元素,因此在使用二路归并排序时关键在于找到链表的中间结点将链表一分为二:可以利用一个步长为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);
-
2015安永成都场笔试经验
阅历了凶残的书面考试...感受我的智商已经走到止境了....但愿对下一年的校招或者实习的童鞋有用....书面考试两个par榜首par是逻辑测验第二par是性情测验榜首par分三块阅览核算图形推理每一块两组题4分钟时刻一到直接跳转.......所以请必定鼠标下手快....对于...
-
公卫执业医师综合笔试知识点总结参考
小儿腮腺炎的症状一、肿脸脸部肿胀是最典型的小儿腮腺炎的症状,腮腺炎患儿的脸部通常表现为一侧或两侧以耳垂为中心向前后扩展的肿,肿大的脸部通常呈半球形,没有明显的边缘界限,用手触摸患儿肿胀的脸部能够感觉到表皮温度较热,并伴随小儿张嘴或咀嚼时有疼痛感。家长...
-
软件测试工程师笔试题及答案
一、判断题(每题2分,20)1、软件测试就是为了验证软件功能实现的是否正确,是否完成既定目标的活动,所以软件测试在软件工程的后期才开始具体的工作。(初级)(×)2、发现错误多的模块,残留在模块中的错误也多。(√)(初级)3、测试人员在测试过程中发现一处问题,如果问题影响不...
-
2017年国考笔试本周末开考需要带哪些物品
1.2B铅笔2B铅笔的用处大家都知道,行测和申论的准考证号都需要,尤其是行测,答题卡全部都是用2B铅笔作答。2B铅笔一定是要在正规超市或大型文具店购买,保证是真的2B铅笔,因为在大学联考就有考生因为买了假的2B铅笔,导致碳粉不能识别,影响分数。2.身份证、准考证身份证和准考...