链表回文判断

链表类型题目注意事项：

1. 需要注意一个节点和空链表的特殊情况。
2. 需要考虑链表中特殊位置的存在的处理方式（tail 和head）
3. 注意循环中使用next时需要判断该节点本身是否存在，如果不存在则不能使用next。
4. 链表类型的题在其他其他数据结构的辅助下进行解题，空间复杂度提高，但是解题会更加的简单。
5. 在进行判断类型题操作的时候，最好不要破坏链表的结构。

案例：请编写一个函数，检查链表是否为回文。

给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。
测试样例：
{1,2,3,2,1}
返回：true
{1,2,3,2,3}
返回：false

思路：

回文概念：顺序遍历和反序遍历结构一致。所以最简单的思路可以利用栈的特性，先将所有的节点压入栈中，然后逐个弹出，与节点作比较。

方法一:

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Palindrome:
    def isPalindrome(self, pHead):
        # write code here
        stack = []
        cur = pHead
        # 将所有的节点压入栈中
        while cur:
            stack.append(cur.val)
            cur = cur.next
        # 出栈并判断是否为回文
        while stack:
            num = stack.pop()
            if num != pHead.val:
                return False
            pHead = pHead.next
        return True

空间复杂度为O(n)

方法二：利用快指针和慢指针来减少对额外空间的使用，可将额外的空间缩少致一般，同时利用了回文的对称性。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Palindrome:
    def isPalindrome(self, pHead):
        # write code here
        # 方法一：O(n)
        slow = pHead
        fast = pHead.next
        stack = []
        # 将前半部分的回文压入到栈中
        while fast and fast.next:
            stack.append(slow.val)
            slow = slow.next
            fast = fast.next.next
        # 注意如果节点为偶数，则慢指针还有一个点没有入栈，需要通过fast指针的状态来判断链表长度为奇数还是偶数。
        if fast:
            stack.append(slow.val)
        slow = slow.next
        # 将栈中的数弹出与回文后半部分做比较
        while stack:
            num = stack.pop()
            if num!=slow.val:
                return False
            slow = slow.next
        return True

方法三：不需要借助额外的空间，将后部分的列表进行反序，并返回反序后的头节点，然后与表头进行逐个比较。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Palindrome:
    def isPalindrome(self, pHead):
        # write code here
        # 方法一：O(n)
        slow = pHead
        fast = pHead.next
        # 将前半部分的回文压入到栈中
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        pre = slow
        cur = slow.next
        nex = cur.next
        # 需要将后半部分进行逆序
        while nex:  # 判断条件需要考虑
            cur.next = pre
            pre = cur
            cur = nex
            nex = nex.next
        cur.next = pre
        while cur.next != slow:
            if cur.val!=pHead.val:
                return False
            cur= cur.next
            pHead = pHead.next
        return True