测试数据

link = [[1, 1], [2, 2], [3, 3], [2, 4], [1, -1]] # 回文链表(奇数长度) 1->2->3->2->1

link = [[1, 1], [2, 2], [2, 3], [1, -1]] # 回文链表(偶数长度) 1->2->2->1

link = [[1, 1], [2, 2], [3, 3], [1, 4], [1, -1]] # 非回文链表(奇数长度) 1->2->3->1->1

link = [[1, 1], [1, 2], [2, 3], [1, -1]] # 非回文链表(偶数长度) 1->1->2->1

link = [[1, -1]] # 单节点链表

link = [[5, 1], [5, 2], [5, -1]] # 所有节点值相同 5->5->5

def array_convert(link): # 数组转换法：将链表值复制到数组，然后用双指针判断回文 values = [] current = 0 # 当前节点索引，从链表头开始 while current != -1: # 遍历链表生成对应数组 values.append(link[current][0]) current = link[current][1] # 待完成1：数组双指针判断回文 if

def fast_slow_reverse(link): # 快慢指针与反转后半部分法：找到中点，反转后半部分，然后比较 if not link: # 空链表直接返回True return True
# 快慢指针找中点 slow, fast = 0, 0 while fast != -1 and link[fast][1] != -1: # 快指针未到达链表末尾 slow = link[slow][1] fast = link[fast][1] if fast != -1: # 如果快指针还没到末尾 fast = link[fast][1] # 快指针再前进一步 # 待完成2：反转后半部分链表 prev = -1 # 前一个节点索引初始化为-1 curr = slow # 当前节点索引从慢指针位置开始

# 比较前后两部分
first, second = 0, prev  # 前半部分和反转后的后半部分
flag = True  # 假设是回文链表
# 待完成3：判断是否回文






# 重新反转后半部分恢复链表原状（非必须，根据实际要求取舍）
curr = prev  # 从反转后的头节点开始
prev = -1  # 重置前驱节点
while curr != -1:  # 遍历反转部分
    next = link[curr][1]
    link[curr][1] = prev
    prev = curr
    curr = next
return flag

def half_stack(link): # 半栈法：将前半部分值压入栈，然后与后半部分比较 if not link: # 空链表直接返回True return True slow, fast = 0, 0 # 初始化快慢指针索引 stack = [] # 创建栈存储前半部分值 top = -1 # 栈顶指针初始化 # 快慢指针找中点 while fast != -1 and link[fast][1] != -1: # 快指针未到达链表末尾 top += 1 stack.append(link[slow][0]) # 将慢指针值压入栈 slow = link[slow][1] fast = link[fast][1] if fast != -1: # 如果快指针还没到末尾，则再前进一步 fast = link[fast][1] if fast != -1: # 处理奇数长度情况。如果快指针不为空，说明链表长度为奇数 slow = link[slow][1] # 跳过中间节点 # 待完成4：比较栈中元素与后半部分链表元素判断是否回文

主程序

print("链表结构:", link) # 打印当前链表结构

调用三种方法判断是否为回文链表

result1 = array_convert(link) # 数组转换法 result2 = fast_slow_reverse(link) # 快慢指针反转法 result3 = half_stack(link) # 半栈法 print("数组转换法结果:", result1) print("快慢指针反转法结果:", result2) print("半栈法结果:", result3) if result1 == result2 == result3: print("三种方法结果一致") else: print("警告：三种方法结果不一致！")