回文链表-python解决方案

题目描述:

请判断一个链表是否为回文链表。

示例 1:

输入:1->2

输出:false

示例 2:

输入:1->2->2->1

输出:true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法1:时间复杂度为O(n),空间复杂度为O(n)的解法

遍历整个链表,获得所有数值,并放入数组中,判断其倒序是否等于本身,相等则返回True,否则返回False.

# Definition for singly-linked list.

# class ListNode:

#    def __init__(self, x):

#        self.val = x

#        self.next = None

class Solution:

    def isPalindrome(self, head):

        temp=[]

        while head!=None:

            temp.append(head.val)

            head=head.next

        if temp==temp[::-1]:

            return True

        else:

            return False

解法2:时间复杂度为O(n),空间复杂度为O(1)的解法

解答来自:https://blog.csdn.net/qiubingcsdn/article/details/82895660

def isPalindrome(self, head):

        """

        :type head: ListNode

        :rtype: bool

        """

        prev = None

        fast = slow = head

        while fast and fast.next:        #翻转链表的前n/2个结点，prev为翻转后的头结点

            fast = fast.next.next

            prev, prev.next, slow = slow, prev, slow.next

        if fast:      #结点个数为奇数时，跳过最中间的结点

            slow = slow.next

        while slow and slow.val == prev.val:        #前n/2个结点翻转后，与剩下的结点进行对比

            prev, slow = prev.next, slow.next

        return not prev

算法真的很奇妙呀!