Palindrome Linked List

Implement a function to check if a linked list is a palindrome.

Example

Given 1->2->1, return true

Solution

1) 利用堆栈纪录前半段的值，然后在判断奇偶，如果是奇数，就在弹出一个。

2) 全部压入stack 中，然后利用堆栈的特性，头入尾出，从新遍历链表，进行比较。

1，2 两种方法大同小异

3） 利用递归的方法，由于递归的栈特性，从后面bubble up, 从而可以间接的实现链表的双指针特性。

1) 

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

class Solution:
    # @param head, a ListNode
    # @return a boolean
    def isPalindrome(self, head):
        # Write your code here
        if head == None or head.next == None:
            return True
        list = []
        fast = head
        slow = head
        list.append(head.val)

        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            list.append(slow.val)
        if fast.next == None:
            list.pop()

        while slow.next:
            slow = slow.next
            if slow.val != list.pop():
                return False
        return True

2) 充分利用递归的堆栈特性，加上链表的next 特性，我们可以间接的实现左右指针的比较，这里不好理解的就是对递归的抽象，由于是traverse 所以定义全局变量，并且定义helper函数，helper的返回值就是链表是回文的，这里比较混淆的就是，传入值，传入值只是告诉函数，我是谁，我是第几个，本质是我们比较的是同一链表，不同的索引而已，

/**

* Definition for singly-linked list.

* public class ListNode {

* public int val;

* public ListNode next;

* public ListNode(int x) { val = x; }

* }

*/

public class Solution {

ListNode left = null;

public bool IsPalindrome\(ListNode head\) {

    left = head;



    return Helper\(head\);

}



public bool Helper\(ListNode sublist\){

    if\(sublist == null\){

        return true;

    }



    bool flag = Helper\(sublist.next\);

    if\(!flag\){

        return false;

    }



    bool y = \(sublist.val == left.val\);



    left = left.next;



    return y;

}

}