题目1 - 将2个递增的有序链表合并为一个有序链表;要求结果链表仍然使用两个链表的存储空间,不另外占用其他的存储空间. 表中不允许有重复的数据
void MergeList(LinkList *list1, LinkList *list2, LinkList *list3) {
LinkList p1,p2,p3,tmp;
p1 = (*list1)->next;
p2 = (*list2)->next;
*list3 = p3 = *list1;
while (p1 && p2) {
printf("%d %d\n",p1->data,p2->data);
if (p1->data == p2->data) {
p3->next = p1;
p3 = p1;
p1 = p1->next;
tmp = p2->next;
free(p2);
p2 = tmp;
} else if(p1->data > p2->data) {
p3->next = p2;
p2 = p2->next;
p3 = p2;
} else {
p3->next = p1;
p3 = p1;
p1 = p1->next;
}
}
// if (NULL == p1) {
// p3->next = p2;
// } else if (NULL == p2) {
// p3->next = p1;
// }
p3->next = p1 ? p1 : p2;
free(*list2);
}
题目2 - 已知两个链表A和B分别表示两个集合.其元素递增排列. 设计一个算法,用于求出A与B的交集,并存储在A链表中; 例如: La = {2,4,6,8}; Lb = {4,6,8,10}; Lc = {4,6,8}
void Intersection(LinkList *list1, LinkList *list2, LinkList *list3) {
LinkList p1,p2,p3,tmp;
p1 = (*list1)->next;
p2 = (*list2)->next;
*list3 = p3 = *list1;
while (p1 && p2) {
if (p1->data == p2->data) {
p3->next = p1;
p3 = p1;
p1 = p1->next;
tmp = p2->next;
free(p2);
p2 = tmp;
} else if (p1->data > p2->data) {
tmp = p2->next;
free(p2);
p2 = tmp;
} else {
tmp = p1->next;
free(p1);
p1 = tmp;
}
}
p3->next = NULL;
if (NULL == p1) {
while (p2) {
tmp = p2->next;
free(p2);
p2 = tmp;
}
}
if (NULL == p2) {
while (p1) {
tmp = p1->next;
free(p1);
p1 = tmp;
}
}
free(*list2);
}
题目3 - 设计一个算法,将链表中所有节点的链接方向"原地旋转",即要求仅仅利用原表的存储空间. 换句话说,要求算法空间复杂度为O(1); 例如:L={0,2,4,6,8,10}, 逆转后: L = {10,8,6,4,2,0};
void Inverse(LinkList *list) {
LinkList p,rear;
p = (*list)->next;
(*list)->next = NULL;
while (p) {
rear = p->next;
p->next = (*list)->next;
(*list)->next = p;
p = rear;
}
}
题目4 - 设计一个算法,删除递增有序链表中值大于等于mink且小于等于maxk(mink,maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)的所有元素;
void DeleteMinMax(LinkList *list, int mink, int maxk) {
LinkList p,q,pre,tmp;
pre = (*list);
p = (*list)->next;
while (p && p->data < mink) {
pre = p;
p = p->next;
}
while (p && p->data <= maxk) {
p = p->next;
}
q = pre->next;
pre->next = p;
while (q != p) {
tmp = q->next;
free(q);
q = tmp;
}
}
题目5 - 设将n(n>1)个整数存放到一维数组R中, 试设计一个在时间和空间两方面都尽可能高效的算法;将R中保存的序列循环左移p个位置(0<p<n)个位置, 即将R中的数据由(x0,x1,......,xn-1)变换为(xp,xp+1,...,xn-1,x0,x1,...,xp-1).
例如: pre[10] = {0,1,2,3,4,5,6,7,8,9},
n = 10,p = 3;
pre[10] = {3,4,5,6,7,8,9,0,1,2}
void Reverse(int *p, int left, int right) {
int i = left;
int j = right;
int tmp;
while (i < j) {
tmp = p[i];
p[i] = p[j];
p[j] = tmp;
i++;
j--;
}
}
void Shift(int *p,int n,int position) {
if (position > 0 && position < n) {
Reverse(p, 0, n - 1);
Reverse(p, 0, n - position -1);
Reverse(p, n-position, n-1);
}
}
题目6 - 已知一个整数序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...= apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主元素; 若B = (0,5,5,3,5,1,5,7),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.
int MainElement(int *A, int n) {
int count = 1;
int key = A[0];
for (int i = 1; i < n; i++) {
if (key == A[i]) {
count++;
} else {
if (count > 0) {
count--;
} else {
key = A[i];
count = 1;
}
}
}
for (int i = 0; i < n; i++) {
if (key == A[i]) {
count++;
}
}
if (count > n/2) {
return key;
}
return -1;
}
题目7 - 用单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计一个时间复杂度尽可能高效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第一次出现的结点,而删除其余绝对值相等的结点.例如,链表A = {21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};
void DeleteEqualNode(LinkList *list, int n) {
int *a = alloca(sizeof(int) * n);
LinkList rear = *list;
for (int i = 0; i < n; i++) {
*(a+i) = 0;
}
LinkList p = (*list)->next;
while (p) {
if (a[abs(p->data)] == 1) {
rear->next = p->next;
free(p);
p = rear->next;
} else {
a[abs(p->data)] = 1;
rear = p;
p = p->next;
}
}
}
网友评论