小黑腰酸背痛继续leetcode:剑指 Offer II 027. 回文链表

小黑做法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        if arr[::-1] == arr:
            return True
        else:
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

递归法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        self.pre_node = head
        def res_check(node = head):
            if node:
                if not res_check(node.next):
                    return False
                if self.pre_node.val != node.val:
                    return False
                self.pre_node = self.pre_node.next
            return True
        return res_check()   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

快慢指针法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        def reserve(head):
            previous = None
            current = head
            while current:
                next_node = current.next
                current.next = previous
                previous = current
                current = next_node
            return previous
        # 初始化快慢结点
        slow = fast = head
        while fast and fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        # slow到中点,翻转后面
        after_reverse = reserve(slow.next)
        # 判断两段是否相等
        after_head = after_reverse
        pre_head = head
        while after_head and pre_head:
            if after_head.val != pre_head.val:
                return False
            after_head = after_head.next
            pre_head = pre_head.next
        return True
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

小黑生活