234 Palindrome Linked List

题目

Palindrome Linked List

题解

因为回文链表从前往后遍历与从后往前遍历得到的结果是一样的，所以如果我们从链表的头尾两端同时向中间遍历的话，就可以检验该链表是否为回文链表。通过运用快慢指针+反转链表的技巧，我们可以在\(O(n)\)的时间复杂度以及\(O(1)\)的空间复杂度以内做到从链表的头尾两端同时向中间遍历。

首先使用快慢指针遍历链表，快指针每次跨过两个节点，慢指针每次跨过一个节点，当快指针到达链表末端时，慢指针恰好指向链表的中间节点。

digraph G {
    {
        rank=same
        A[label="1"]
        B[label="6"]
        C[label="4"]
        D[label="5" color="blue" style="filled"]
        E[label="4"]
        F[label="6"]
        G[label="1" color="red" style="filled"]
    }
    A -> B -> C -> D -> E -> F -> G
    A:n -> C:n -> E:n -> G:n [arrowhead="none", color="red"]
    A:s -> B:s -> C:s -> D:s [arrowhead="none", color="blue"]

    {
        node[shape=plain]
        fast
        slow
    }
    G -> fast [dir=back]
    D -> slow [dir=back]
}

获取中间节点之后，我们把后半段链表逐个节点进行反转，反转之后即可得到链表的末尾节点，此时我们就可以从链表的头尾两端同时向中间遍历以检验该链表是否为回文链表了。

digraph G {
    {
        rank=same
        A[label="1"]
        B[label="6"]
        C[label="4"]
        D[label="5" color="blue" style="filled"]
        E[label="4"]
        F[label="6"]
        G[label="1"]
    }
    A -> B -> C -> D
    D -> E -> F -> G [dir="back" color="red"]

    {
        rank = same
        node[shape=plain]
        head
        slow
        tail
    }
    D -> slow [dir=back]
    A -> head [dir=back]
    G -> tail [dir=back]
}

代码

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast = head
        slow = head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next

        middle = slow
        previous = None
        current = middle
        while current is not None:
            temp = current.next
            current.next = previous
            previous = current
            current = temp

        head_node = head
        tail_node = previous
        result = True
        while tail_node is not None:
            if head_node.val != tail_node.val:
                result = False
                break
            tail_node = tail_node.next
            head_node = head_node.next

        return result