[数据结构与算法]LeetCode 234. 回文链表

1、题目

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

示例 1:

输入: 1->2
输出: false

2、解答

这道题其实要想清楚如何判断是否回文。有两种思路，一种就是从首尾两端一一对比；一种是找到中间位置，然后比较前后两部分。

• 前后指针法：就是把链表转换成数组，然后比较数组是否回文。
• 栈空间法：这个也是思路一的实现，只不过借用了栈。
• 递归法：这个算比较巧妙吧，递归找到链表结尾，然后根据递归的特性，反过来遍历这个链表。
• 快慢指针法：前面三个是思路一的实现，这种事思路二的实现。维护快慢两个指针，然后找到中间位置，再翻转后半指针，和前半部分比较。这种思路空间复杂度是O(1)。

class Solution(object):
    def isPalindrome(self, head):
        """
        双指针法:就是从这个链表首尾两端开始遍历，依次比较左右两个指针值是否相等即可
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True

        node_values = []
        while head is not None:
            node_values.append(head.val)
            head = head.next
        left = 0
        right = len(node_values) - 1
        while left <= right:
            if node_values[left] != node_values[right]:
                return False
            left += 1
            right -= 1
        return True

    def isPalindrome2(self, head):
        """
        栈：这个和双指针其实类似，就是借助了栈这个数据结构
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        node_stack = []
        temp = head
        while temp is not None:
            node_stack.append(temp.val)
            temp = temp.next
        while len(node_stack)>0:
            if node_stack.pop(0)!=head.val:
                return False
            head = head.next
        return True


    def isPalindrome3(self, head):
        """
        递归法：这个方法其实也是先递归到链表最底部再和首部比较
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        self.gobal = head

        return self.back_trace(head.next)


    def back_trace(self, head):
        if head is None:
            return True

        if self.back_trace(head.next):
            if self.gobal.val==head.val:
                self.gobal = self.gobal.next
                return True
        return False

    def isPalindrome4(self, head):
        """
        快慢指针法：这个是先找到中间点再比较
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True

        fast = low = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            low = low.next
        # 这步操作是用来移动到整个链表的后面部分再翻转
        low = low.next
        reversal_next = self.reversal_node(low)
        while reversal_next is not None:
            if reversal_next.val!=head.val:
                return False
            reversal_next = reversal_next.next
            head = head.next
        return True