LeetCode练习——链表（回文链表）_链 回文 leetcode

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

官方解法：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/

解法一：将值复制到数组中后用双指针法
一共为两个步骤：

• 复制链表值到数组列表中。
• 使用双指针法判断是否为回文。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        current_node = head
        while current_node is not None:
            vals.append(current_node.val)
            current_node = current_node.next
        return vals == vals[::-1]  # 列表的反向副本
1
2
3
4
5
6
7
8

时间复杂度：O(n)，其中 n 指的是链表的元素个数。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

解法二：递归（遍历结点更优雅，但空间复杂度仍为O(n)）

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:

        self.front_pointer = head

        def recursively_check(current_node=head):
            if current_node is not None:
                if not recursively_check(current_node.next):
                    return False
                if self.front_pointer.val != current_node.val:
                    return False
                self.front_pointer = self.front_pointer.next
            return True

        return recursively_check()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解法三：快慢指针
整个流程可以分为以下五个步骤：

• 找到前半部分链表的尾节点。
• 反转后半部分链表。
• 判断是否回文。
• 恢复链表。
• 返回结果。

执行步骤一，可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。
也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
若链表有奇数个节点，则中间的节点应该看作是前半部分。
步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。
步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。
步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

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
        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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

时间复杂度：O(n)，其中 n 指的是链表的大小。
空间复杂度：O(1)。只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。

力扣 (LeetCode)链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/