leetcode 234： 判断是否是回文链表

image.png

链表的定义：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

链表的构建：

vals = [1, 2, 3, 3, 2, 1]
# vals = [1, 2, 3, 4, 3, 2, 1]
num = len(vals)
root = ListNode(vals[0])
p = root
for i in range(1, num):
    p.next = ListNode(vals[i])
    p = p.next

构建出来的链表为：1->2->3->3->2->1或者1->2->3->4->3->2->1，都是属于回文链表。

最简单的方法，将链表的元素存入列表，然后通过索引判断是否为回文链表，时间复杂度为O(n), 空间复杂度为O(n)

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head: return True
        res = []
        while head:
            res.append(head.val)
            head = head.next
        
        num = len(res)
        for i in range(num//2):
            if res[i] != res[-(i+1)]:
                return False
        return True

题目中进阶要求空间复杂度为O(1), 可以使用原地反一部分转链表再比较的方法。

整个流程可以分为以下五个步骤：
（1）找到前半部分链表的尾节点（可以统计链表的长度，然后再遍历得到中间节点。更快的方法是用快慢指针，快指针每次走两步，慢指针每次走一步，当快指针走到链表的结尾时，慢指针走到中间节点）。
（2）反转后半部分链表。
（3）判断是否回文。
（4）恢复链表（题目不要求，但是最好还原）。
返回结果。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return True
        # 找到前半部分链表的尾节点并反转后半部分链表
        # 如果是奇数个，找到的是最中间的节点
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)
        # 判断是否回文
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next

        # 还原链表并返回结果
        first_half_end.next = self.reverse_list(second_half_start)
        return result

    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
            print(slow.val)
            print(fast.val)
        return slow

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous

测试代码：

res_str = test_object.isPalindrome(root)
print(res_str)

部分代码来自：
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）