链表习题
一、链表概念
关于链表概念请参照严蔚敏版《数据结构》
二、例题
PAT甲级1032
题目大意:找出两个字符串的公共后缀
输入样例,每组输入的第一行为,第一个串的首地址,第二个串的首地址,节点个数;以下的每一行为,当前节点地址、当前节点值、下一个节点的地址
大致意思如上图
算法思路:可以用一个静态链表来存储数据,这样更加方便操作,关于静态链表的概念可以参考《数据结构》,可以先对一条链表进行操作,操作过程中对于所有被操作过的元素进行标记,再对第二条链表进行遍历时如果遇到第一个被标记的元素,说明该元素就是首个公共节点,返回地址就行。
代码
扩展:对于这种求公共后缀的题目(2012年408算法题),其实如果给出的是字符串可以尝试从后向前遍历字符串找出公共后缀,因为字符串是一个数组支持随机存取,如果题目要求用链表实现可以定义两个链表指针,过滤长字符串的前数个元素,然后让两个指针同时向后遍历,当出现相同数据时,说明两个指针指向公共后缀