云野 ☁️

26、回文链表

|
|
访问
本文共578字。
展开

回顾：[3.24]

题目描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

image-20220324162717973

1
2
输入：head = [1,2,2,1]
输出：true

我的思路：构建一个新链表，存放翻转后的链表；判断两者是否相等，相等返回True

方法1、转数组，双指针

执行用时： ms

时间复杂度：O(n)

链表赋值给数组，O(n)。回文判断是否相等执行了O(n/2)，即还是O(n)。总的为O(2n)，所以最终就是O(n)。

空间复杂度：O(n)

使用了一个大小为n的数组存放。

思路总结：

1、复制链表的值给数组

2、双指针，一前一后，向中间遍历，判断是否相等。知道两个指针相遇。

注意：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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:
        l = list()
        cur = head
        while cur:
            l.append(cur.val)
            cur = cur.next
        # return l == l[::-1]
        lens = len(l)
        first, end = 0, lens-1
        while end-first >= 1:
            if l[first] != l[end]:
                return False
            first +=1
            end -= 1
        return True

方法2、快慢指针

执行用时：772 ms, 在所有 Python3 提交中击败了19.81%的用户

内存消耗：40.3 MB, 在所有 Python3 提交中击败了79.00%的用户

时间复杂度：O(n)，其中 n 指的是链表的大小。

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

思路总结：1、找到链表的中间值（利用快慢指针）；2、反转后半链表；3、对比前后链表是否相同，相同返回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
33
34
35
36
37
38
39
40
# 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:
        # 快慢指针
        if head is None:
            return True
        fast, slow = head, head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        slow = self.reverseList(slow.next)
        fast = head
        while slow:
            if fast.val != slow.val:
                return False
            else:
                fast = fast.next
                slow = slow.next
        return True
    
    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre
        # if head == None or head.next == None:
        #     return head
        # p = reverseList(head.next)
        # head.next.next = head
        # head.next = None
        # return p