Question

一道算法题

有如下算法
S ← ( L )
S ← a
L ← L , S
L ← S

要求得到
1.( a , a )
2. ( a , ( a , a ) )
3. ( a , ( ( a , a ) , ( a , a ) ) )

Answer 1

，也就是说其中的元素是按照递增或递减的顺序排列且无重复，按照你给的答案来看，A和B应该是递增的。 “pa^.data>=pb^.data”是一个循环条件，作用是避免程序做无意义的动作，举个例子来解释：
假设：A链表的元素是 3 4 5 6
B链表的元素是 1 2 3 4 5 6 7 8 9
初始时，pa指向3，pb指向1，因为3>=1，所以pb会向后移动，依次指向2 3…当pb指向3时，pa.data=pb.data，pa pb同时移动到下一位…进行新的循环比较，直至其中任一单链表中所有元素都比较完。若比较结果有完全吻合的元素序列则返回“true”，否则返回“false”。
假设：A链表的元素是 3 4 5 6
B链表的元素是 5 6 7 8 9 10 11 12
初始时，pa指向3，pb指向5，因为3<5，pb第一个元素已经大于pa第一个元素了，而pb又是递增的，后面的元素也一定都大于3，所以已经可以判定pb不可能包含pa，此时如果再让算法继续去比较就没有意义了，所以在前面加了循环条件，不要小看它，当链表很长时它可以大大提高算法的效率。
PS：如果A和B是递减的，那么循环条件应改为“pa^.data<=pb^.data”。
另外,站长团上有产品团购,便宜有保证

Answer 2

箭头画反了吧？
最左推导如下：
1. S -> (L) --> (L,S) -->(S,S) -->(a,S) -->(a,a)
2. S -> (L) --> (L,S) -->(S,S) -->(a,S)--->(a,(L)) 然后从L-->a,a
3. 基本类似2