Leetcode-234.回文链表

Leetcode
1.4k 词

image.png

思路

判断链表是否为回文，可以通过快慢指针找到链表中点，然后反转后半部分链表，接着从头和反转后的部分逐一比较值是否相等。为了达到 O(1) 空间复杂度，我们不能使用数组或栈辅助存储值，必须在原链表上操作。

解题过程

边界判断：如果链表为空或只有一个节点，直接返回 True。

找中点：使用快慢指针，fast 每次走两步，slow 每次走一步，slow 停下时刚好位于链表中点。

反转后半部分：从 slow 开始反转链表，获得 reverse_head。

比较是否相等：用两个指针，分别从 head 和 reverse_head 出发，同时遍历并比较值是否一致。

返回结果：只要有任意一组值不一致，就返回 False；否则返回 True。

复杂度分析

时间复杂度：O(n)
找中点：O(n)
反转链表：O(n)
比较两半链表：O(n)
空间复杂度：O(1)
只用了若干指针变量，无额外数据结构

实现链表翻转功能

双指针解法：
定义好一个cur和一个pre的指针
cur=head
pre=none
现在的目的是把链表的指向改变。
先考虑第一个元素时
在链没断之前，先用temp指针保存好第二个节点。
修改第一个节点的指向。直接就是cur.next=pre,第一个节点指向pre的节点。
紧接着pre后移动一位移到cur，cur移动到temp

实现找中点功能

找中点：
使用快慢指针，fast 每次走两步，slow 每次走一步，slow 停下时刚好位于链表中点。偶数个节点，最终选的是靠右边的节点。终止的信号是快指针或者快指针的next为空指针。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def reverseList(self,head: Optional[ListNode]) -> Optional[ListNode]:

        pre,cur=None,head

        while cur:

            temp=cur.next

            cur.next=pre

            pre=cur

            cur=temp

        return pre

    def middleNote(self,head: Optional[ListNode]) -> Optional[ListNode]:

        slow=fast=head

        while fast and fast.next:

            slow=slow.next

            fast=fast.next.next

        return slow

    def isPalindrome(self, head: Optional[ListNode]) -> bool:

        mid=self.middleNote(head)

        reverse=self.reverseList(mid)

        while reverse:

            if head.val!=reverse.val:

                return False

            head=head.next

            reverse=reverse.next

        return True