设单链表的表头指针为h,节点结构由data和next两个域组成,其中data域为字符型,写出算法issymmetric(linklist h),判断该链表的所有字符是否中心对称。例如xyx,xyyx都是中心对称.
时间: 2023-04-26 14:06:36 浏览: 130
编写算法,利用栈判断所给字符是否具有中心对称关系。要求有尽可能少的时间完成判断。
算法issymmetric(linklist h):
1. 定义两个指针slow和fast,初始时都指向链表的头节点h。
2. 定义一个栈stack,用于存储slow指针遍历过的节点的data域。
3. 遍历链表,当fast指针指向的节点不为空时,执行以下操作:
a. 将slow指针指向的节点的data域压入栈中。
b. 如果fast指针能够向后移动两个节点,则将fast指针向后移动两个节点,否则将fast指针向后移动一个节点。
c. 将slow指针向后移动一个节点。
4. 遍历完链表后,如果链表长度为奇数,则将slow指针向后移动一个节点,因为中心节点不需要比较。
5. 从栈中弹出元素,与slow指针指向的节点的data域比较,如果不相等,则链表不是中心对称的,返回false;否则继续比较,直到栈为空或者比较完所有节点。
6. 如果比较完所有节点,都相等,则链表是中心对称的,返回true。
阅读全文