|
题目：设A=(a1,a2,…,an)，B=(b1,b2,…,bm)是两个递增有序的线性表（其中n、m均大于1），且所有数据元素均不相同。假设A、B均采用带头节点的单链表存放，设计一个尽可能高效的算法判断B是否为A的一个子序列，并分析算法的时间复杂度和空间复杂度。
采用二路归并思路，用p、q分别扫描有序单链表A、B，先找到第一个两者值相等的节点，然后在两者值相等时同步后移，如果B扫描完毕返回1，否则返回0。对应的算法如下：
本算法的时间复杂度为O(m+n)，空间复杂度为O(1)。其中m、n分别为A、B单链表的长度。
typedef struct linkList {
int data;
struct linkList* next;
}linkList;
int subSeq(linkList* a, linkList *b) {
linkList* p = a->next;
linkList* q = b->next;
while (q != NULL && p != NULL) {
if (p->data < q->data) {
//A表中p指向的值小于B表中q指向的值，则p后移
p = p->next;
}
else if (p->data > q->data) {
//A表中p指向的值大于B表中q指向的值，则q后移
q = q->next;
}
else if(p->data==p->data){
//相等则同时后移
p = p->next;
q = q->next;
}
}
//循环结束后，若q为null则比较完成
//B中节点比较完毕,并且A表中p必须有往后移动返回1
//比如：A：4，5，6，B：2，3,这种情况下，结束循环，指向A表的p指针没有移动，也是比较失败的
if (q == NULL&&p!=a->next->data) {
return 1;
}
else {
return 0;
}
}
|