回文链表（Leetcode）

题目

给你一个单链表的头节点 $head$ ，请你判断该链表是否为

回文链表。如果是，返回 $true$ ；否则，返回 $false$ 。

解题

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef isPalindrome(head: ListNode) -> bool:if not head or not head.next:return True# 快慢指针找到链表中点slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.next# 反转链表后半部分prev = Nonewhile slow:temp = slow.nextslow.next = prevprev = slowslow = temp# 比较前半部分和反转后的后半部分left, right = head, prevwhile right:if left.val != right.val:return Falseleft = left.nextright = right.nextreturn Truedef print_linked_list(head):while head:print(head.val, end=" -> ")head = head.nextprint("None")def create_linked_list(arr):if not arr:return Nonehead = ListNode(arr[0])current = headfor val in arr[1:]:current.next = ListNode(val)current = current.nextreturn head# 测试用例
def test_isPalindrome():test_cases = [[1, 2, 2, 1],[1, 2, 3, 2, 1],[1, 2, 3, 4, 5],[1, 2],[1],[]]for i, values in enumerate(test_cases):head = create_linked_list(values)print(f"Test case {i + 1}:", )print_linked_list(head)result = isPalindrome(head)print(f"Result: {result}\n")# 运行测试
test_isPalindrome()

Test case 1:
1 -> 2 -> 2 -> 1 -> None
Result: True

Test case 2:
1 -> 2 -> 3 -> 2 -> 1 -> None
Result: True

Test case 3:
1 -> 2 -> 3 -> 4 -> 5 -> None
Result: False

Test case 4:
1 -> 2 -> None
Result: False

Test case 5:
1 -> None
Result: True

Test case 6:
None
Result: True