题目一
将2个递增的有序链表合并为一个链表的有序链表；要求结果链表仍然使用两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。
解析：
所需结果：L1 {1,2,3,4}; L2 {3,5,6,7,8,9} ==> L3 {1,2,3,4,5,6,7,8,9}。
要求：1：使用L1，L2现有存储空间，不占用其他存储空间，即空间复杂度为 O(1)。
2：表中不允许有重复数据。需要释放重复的节点数据。
思路：使用 单链表结构
1：L3 指向L1，遍历L1 L2，取较小元素存储在L3；
2：相等的元素，释放掉L2的元素；
3：未遍历到的元素，拼接到L3后，返回L3；
void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc) {
LinkList pa,pb,pc;
//pa 是链表La的工作指针,pb 是链表Lb的工作指针, 初始化为首元结点;
pa = (*La)->next;
pb = (*Lb)->next;
*Lc = pc = *La;
while (pa && pb) {
if (pa->data < pb->data) {
pc->next = pa;//取较小者La中的元素
pc = pa; //,将pa链接在pc的后面
pa = pa->next;//,pa指针后移
} else if(pa->data > pb->data){
pc->next = pb;//取较小者Lb的元素
pc = pb; //将pb链接在pc后面
pb = pb->next;// pb指针后移
} else {
pc->next = pa;//相等时取La中的元素
pc = pa;
pa = pa ->next;
LinkList temp = pb->next;
free(pb);//,删除Lb的元素;
pb = temp;
}
}
//将非空表的剩余元素之间链接在Lc表的最后
pc->next = pa?pa:pb;
//释放Lb的头结点
free(*Lb);
}
题目二
已知两个链表A B 分别表示两个集合，其内元素递增，设计一个算法，求出AB的交集，并存储到A链表中。
解析：
所需结果：LA {1,2 ,3,4}; LB {2,3,4,6,7,8,9} ==> LC {2,3,4}。
要求：1：交集存到A中，即空间复杂度为 O(1)。
思路：使用单链表结构
1：LC指向LA，遍历LA LB(不为空)；
2：元素相等，LA节点连接到LC，LB节点释放，元素较小者，删除；
3：未遍历到的元素，释放。
void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc) {
LinkList pa,pb,pc,temp;
//pa 是链表La的工作指针,pb 是链表Lb的工作指针, 初始化为首元结点;La的头结点作为Lc的头结点;
pa = (*La)->next;
pb = (*Lb)->next;
*Lc = pc = *La;
while (pa && pb) {
if (pa->data == pb->data) {
//相等,交集并入结果链表中;
//(1).取La中的元素,将pa链接到pc的后面,pa指针后移;
pc->next = pa;
pc = pa;
pa = pa->next;
//(2)删除Lb中对应相等的元素
temp = pb;
pb = pb->next;
free(temp);
}else if(pa->data < pb->data){
//删除较小值La的元素;
temp = pa;
pa = pa->next;
free(temp);
}else{
//删除较小值Lb中的元素
temp = pb;
pb = pb->next;
free(temp);
}
}
pc->next = NULL;//以上代码交集取全了，尾节点next 置为NULL
while (pa) { //Lb为空,删除非空表La中的所有元素
temp = pa;
pa = pa->next;
free(temp);
}
while (pb) {//La为空,删除非空表Lb中的所有元素
temp = pb;
pb = pb->next;
free(temp);
}
free(*Lb);
}
题目三
设计一个算法，将链表中的所有节点的链接方向原地旋转，及要求仅仅利用原表的存储空间，即要求空间复杂度为O(1)。
例如：L= {0,2,4,6,8,10}, 逆转后：L = {10,8,6,4,2,0}
要求：链表逆转，空间复杂度 O(1)。
思路：使用单链表 头插法 可逆转链表。（头插法生成的列表，为逆序的）
void Inverse(LinkList *L){//目的: 逆转带头结点单链表L;
LinkList p,q;
p = (*L)->next; //p指向首元结点;
(*L)->next = NULL; //头结点的指针域置空
//遍历链表
while (p!=NULL) {//头插法
q = p->next;//q执行p的后继
p->next = (*L)->next;//p->next = (*L)->next
(*L)->next = p; //*p 插入到头结点之后;
p = q; //处理下一个结点
}
}
题目四
设计一个算法，删除递增有序链表中值 >= mink 且 <= maxk(mink,maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同)的所有元素；
La={0,2,4,6,8,10},mink = 2,maxk = 8 ==> La={0,10};
思路：1：遍历链表，找到第一个大于mink的节点，用pre保存；
2：遍历链表，找到第一个大于maxk的节点，用p指向；
3：删除元素，修改指针指向，pre->next = p;
4：介于pre 和 p 之间的节点释放；
时间复杂度O(n) 空间复杂度 O(1)
void DeleteMinMax1(LinkList *L, int mink, int maxk){
if (*L == NULL || mink > maxk) {
return;
}
LinkList p,pre = NULL,temp;
p = (*L)->next;
while (p) {
if (p->data < mink) {//找到小于mink最近的节点pre
pre = p;
}
if (p->data > maxk) {//p指向maxk后一个节点
break;
}
p = p->next;
}
LinkList q = pre->next;//3.修改待删除的结点指针
pre->next = p;//删除元素，修改指针指向
while (q != p) {//释放mink——maxk之间的元素
temp = q->next;
free(q);
q = temp;
}
}
题目五
设将n(n>1)个整数存放到一位数组R中，试设计一个在时间空间上都高效的算法，将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(x0,x1...,xn-1)变换为(xp,xp+1,...xn-1,x0,x1,...xp-1)。
所需结果：La={1,2,3,4,5} 左移p=2个位置 ==> La={3,4,5,1,2}。
思路：1：n个数据逆序 5，4，3，2，1;
2：拆解成[5,4,3] [2,1];
3：n-p数据/p个数据，再次逆序[3,4,5][1,2] ==>[3,4,5,1,2]
时间复杂度 O(n) 空间复杂度O(1)
void Reverse(int *pre,int left ,int right) { //将数组R中的数据原地逆置
//i等于左边界left,j等于右边界right;
int i = left,j = right;
int temp;
while (i < j) { //交换pre[i] 和 pre[j] 的值
//交换
temp = pre[i];
pre[i] = pre[j];
pre[j] = temp;
//i右移,j左移
i++;
j--;
}
}
void LeftShift(int *pre,int n,int p){ //将长度为n的数组pre 中的数据循环左移p个位置
if (p>0 && p<n) {
//1. 将数组中所有元素全部逆置
Reverse(pre, 0, n-1);
//2. 将前n-p个数据逆置
Reverse(pre, 0, n-p-1);
//3. 将后p个数据逆置
Reverse(pre, n-p, n-1);
}
}
题目六
已知一个整数序列A={a0,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.
解析：要求找出主元素，主元素出现的次数> n/2;
思路：1：选出首元素A[0]作为候选主元素key，遍历计数count 遇到下一个元素相同则++，不同则--，count<0则，更换key，count置为1，继续遍历选出候选的key。
2：若count>0 ,再次遍历出Key出现的次数count；
3：若 count > n/2 则返回 key值，否则 返回-1；
时间复杂度O(n); 空间复杂度O(1)。
int MainElement(int *A, int n){ //目标: 求整数序列A中的主元素;
int count = 1; //count 用来计数
int key = A[0]; //key 用来保存候选主元素, 初始A[0]
for (int i = 1; i < n; i++) {//(1) 扫描数组,选取候选主元素
//(2) 如果A[i]元素值 == key ,则候选主元素计数加1;
if (A[i] == key) {
count++;
}else{
//(3) 当前元素A[i] 非候选主元素,计数减1;
if(count >0){
count--;
}else{
//(4) 如果count 等于0,则更换候选主元素,重新计数
key = A[i];
count = 1;
}
}
}
//如果count >0
if (count >0){
//(5)统计候选主元素的实际出现次数
for (int i = count = 0; i < n; i++)
if (A[i] == key) count++;
}
//(6)判断count>n/2, 确认key是不是主元素
if (count > n/2) return key;
return -1; //不存在主元素
}
题目七
用单链表保存m个整数，节点的结构为（data,link）且 |data|<=n (n为正整数)。现在要去设计一个时间复杂度尽可能高效的算法。对于链表中的data 绝对值相等的节点，仅保留第一次出现的节点，而删除其余绝对值相等的节点。
例如，链表A= {21,-15,15,-7,15},删除后的链表A={21,-15,-7}；
思路：可以用空间换取时间，定义一个n大小的数组;
1：申请大小为n的辅助数组a,并赋值初值为0;
2： 从首元结点开始遍历链表,依次检查a[|data|]的值, 若[|data|]为0,即结点首次出现,则保留该结点,并置a[|data|] = 1,若t[|data|]不为0,则将该结点从链表中删除.
时间复杂度O(m)(m链表的长度) 空间复杂度O(n)。
void DeleteEqualNode1(LinkList *L,int n) {
int *a = alloca(sizeof(int)*n);//1. 开辟辅助数组a.
for (int i = 0; i < n; i++) {
*(a+i) = 0;//赋值0
}
LinkList r = *L;
LinkList p = r->next;
//{21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};
while (p != NULL) {
if (a[abs(p->data)] == 1) {//如果该绝对值已经在结点上出现过,则删除该结点
r->next = p->next;
free(p);
p = r->next;
} else {
a[abs(p->data)] = 1;//未出现过的结点,则将数组中对应位置置为1;
r = p;
p = p->next;
}
}
}
网友评论