永远是深夜有多好. 我是中国人 灭掉小日本,解放全世界 尊严只在剑锋之上,真理只在大炮的射程之内! 吾视之这小小倭贼,尽是鼠辈_{黄沙百战穿金甲,不破日本终不还</p>}

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：数组双指针判断回文
    





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("警告：三种方法结果不一致！")