计算机408-考研-跨行-判断单链表中序列B是否为序列A的连续子序列的算法设计

Question

问题：
两个整数序列A=(a1,.., an)和B=(b1,...,bn)已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。

注意：
这是数据结构的一道综合应用题，不需要完整的程序代码，只需要符合要求的代码片段

书本解答：

int pattern(LinkList A,LinkList B){
    LNode *p=A;        //p为A链表的工作指针，本题假设A和B均无头结点 
    LNode *pre=p;      //pre记住每趟比较中A链表的开始结点 
    LNode *q=B;        //q是B链表的工作结点 
    while(p&&q){
        if(p->data == q->data){
            p=p->next;
            q=q->next;    
        }else{
            pre=pre->next;
            p=pre;     //A链表开始新的比较结点
            q=B;       //q从B链表第一个结点开始 
        }
    }
    if(q==NULL)        //B已经比较结束 
        return true;   //说明B是A的子序列 
    else
        return false;   //说明B不是A的子序列 
} 

疑问：
pre的存在是否有必要？为什么不能通过p=p->next直接代替pre=pre->next;p=pre;？

我的代码：

int pattern(LinkList A,LinkList B){
    LNode *p=A;        //p为A链表的工作指针，本题假设A和B均无头结点  
    LNode *q=B;        //q是B链表的工作结点 
    while(p&&q){
        if(p->data == q->data){
            p=p->next;
            q=q->next;    
        }else{
            p=p->next;
            q=B;       //q从B链表第一个结点开始 
        }
    }
    if(q==NULL)        //B已经比较结束 
        return true;   //说明B是A的子序列 
    else
        return false;   //说明B不是A的子序列 
} 

Answer 1

pre的作用是遍历一次序列A链表，来查找它的连续子序列 B 链表 。具体就是：有整数序列A=(a1,.., an)，起始时 p 、pre都指向 a1，q 指向 b1，当 p->data != q->data 时，pre = pre->next; 此时 pre 指向了 a2，接着让 p = pre；也就是让 p 也指向 a2，同时让 q = B；也就是让 q 重新指向 b1，然后进行下一轮的从 a2 开始的序列比较，如果还是不同，pre = pre->next；pre 即指向 a3，p 也调整到 a3，q 重新指向 b1，再继续比较。如果找到一直相同，那么直到 q = NULL 时即序列 B 表尾，跳出 while()循环，表示找到了。