チェーンテーブルが返信構造Python版かどうかを判断する

タイトル:チェーンテーブルが返信構造であるか否かを判断し、Trueを返す場合、そうでなければFalseを返す.例えば、チェーンテーブルが[2,5,12,198,12,5,2]であり、Trueを返し、チェーンテーブルが与えられた[2,5,12,198,12,54,20]であり、Falseを返す.
方法1:空間複雑度o(n)で、1つのスタックを使用して、チェーンテーブルのデータをすべてスタックにpushし、チェーンテーブルをもう一度反復し、スタックの値を1つずつ比較し、異なる場合は回文チェーンテーブルではないことを説明します.コード:このコードの中で、私は自分で書いたスタックのデータ構造を使って、方法はすべて別のblogの中に置いて、キューとスタックのデータ構造Python版

    def is_palindrome1(head):
        '''
                     ，      True，     False
          1：     o(n),     o(n)
        '''
        if head == 0 or head.next == 0:
            return True
        p = head
        stack = Stack()  #      Stack     ，     python    list   
        while p != 0:
            stack.push(p.value)
            p = p.next
        p = head
        while p != 0:
            if p.value != stack.pop():
                return False
            p = p.next
        return True

方法2:逆逆逆シーケンスチェーンテーブルの操作空間の複雑さはO(1)であるため,後半のチェーンテーブルを逆シーケンスし,チェーンテーブルの両端からそれぞれ遍歴し,異なるものがあればチェーンテーブルが回文構造ではないことを示す.このように,時間的複雑度は変わらず,空間的複雑度はo(1)である.コード:

    def is_palindrome2(self, head):
        '''
                     ，      True，     False
          2：     o(n),     o(1)，                ，      ，     ，     
        '''
        p, length = head, 0
        while p != 0:
            length += 1
            p = p.next

        mid = (length+1) / 2 - 1
        p = head
        for _ in xrange(mid):
            p = p.next

        mid_node = p  #       
        tail = mid_node.next
        mid_node.next = 0

        pre = mid_node
        while tail != 0:
            p = tail.next
            tail.next = pre
            pre = tail
            tail = p

        p = head
        tail = pre
        #print "p.value", p.value, p.next.value, p.next.next.value, p.next.next.next
        #print "tail.value:", pre.value, pre.next.value, pre.next.next.value, pre.next.next.next.value
        while p != 0:
            #print "p.value:", p.value, "tail.value:", tail.value
            if p.value != pre.value:  #          ，     0，          。
                pre = 0
                while tail != 0:
                    next = tail.next
                    tail.next = pre
                    pre = tail
                    tail = next
                mid_node.next = pre.next
                return False
            else:
                p = p.next
                pre = pre.next
        pre = 0
        while tail != 0:
            next = tail.next
            tail.next = pre
            pre = tail
            tail = next
        mid_node.next = pre.next
        return True

体得:コアは,チェーンテーブルの逆順序空間複雑度が3つの変数にすぎないことである.