回文鎖表——O(n)時間複雑度とO(1)空間複雑度解法

参照リンク:234.Palindrome Linked List [easy] (Python)
このブロガーは3つの解法をまとめた.

単一チェーンテーブルのノード値を1つの配列に記録し、配列が文を返すかどうかを判断する.(または、1回の遍歴で単一チェーンテーブルを双方向チェーンテーブルに拡張し、返信するかどうかを判断します.)——時間O(n),空間O(n)

は、回文が主に前半と後半の比較であると判断し、前半をスタックに圧入して、順次出スタックして後半と比較できれば、回文の有無を判断することができる.--時間O(n),空間O(n/2)

同様の考え方2では,返信文は主に前半と後半の比較であると判断し,後半を反転(依然として単鎖表)できれば,返信文の判断を容易にすることができる.時間O(n),空間O(1)

実験により,このブロガーが提供したコードにバグがあることが分かったが,構想は問題なく,修正してまとめた.
主な知識点は次のとおりです.

「スローポインタ」は、スローポインタの原理と応用について、スローポインタに関するいくつかの応用詳細

を参照することができる.

「チェーンテーブルの反転」は、チェーンテーブルの反転の図文説明(再帰と反復の2つの実装)

を参照することができる.
第3の,時間複雑度O(n),空間複雑度O(1)のアルゴリズムを実現し,まず中位ノードを見つけ,その後後半を反転し,次いで逐一比較した.コードは次のとおりです.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if (head is None) or (head.next is None):
            return True
        # slow fast pointer, find the middle point
        middleNode = self.middleNode(head)
        # reverse the last half of the linkList
        slow = self.reverseList(middleNode)
        while slow is not None:
            if head.val != slow.val:
                return False
            head = head.next
            slow = slow.next
        return True
            
    def reverseList(self, head):
        if head is None:
             return None
        present = head
        new_head = None
        while present is not None:
            cur = present.next
            present.next = new_head
            new_head = present
            present = cur
        return new_head
    
    def middleNode(self, head):
        fast = head
        slow = head
        while (fast is not None) and (slow is not None):
            if fast.next is None:
                return slow
            elif (fast.next is not None) and (fast.next.next is None):
                return slow.next
            else:
                fast = fast.next.next
                slow = slow.next