## Question

### Problem Statement

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

#### Example

Given 1->2->1, return true

#### Challenge

Could you do it in O(n) time and O(1) space?

## 题解1 - 使用辅助栈

### Python

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

class Solution:
# @return a boolean
return True

stack = []
while fast and fast.next:
stack.append(slow.val)
slow = slow.next
fast = fast.next.next

# for even numbers add mid
if fast:
stack.append(slow.val)

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


### Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* @return a boolean
*/

Deque<Integer> stack = new ArrayDeque<Integer>();
// find middle
while (fast != null && fast.next != null) {
stack.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}

// skip mid node if the number of ListNode is odd
if (fast != null) slow = slow.next;

ListNode rCurr = slow;
while (rCurr != null) {
if (rCurr.val != stack.pop()) return false;
rCurr = rCurr.next;
}

return true;
}
}


## 题解2 - 原地翻转

1. 找中点。
2. 翻转链表的后半部分。
3. 逐个比较前后部分节点值。
4. 链表复原，翻转后半部分链表。

### Python

# class ListNode:
#     def __init__(self, val):
#         self.val = val
#         self.next = None
class Solution:
return True

while fast and fast.next:
fast = fast.next.next
slow = slow.next

mid = slow.next
# break
slow.next = None
return False
return True

dummy = ListNode(-1)
return dummy.next


### Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* @return a boolean
*/

// find middle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// skip mid node if the number of ListNode is odd
if (fast != null) slow = slow.next;

// reverse right part of List
while (rCurr != null) {
if (rCurr.val != lCurr.val) {
return false;
}
lCurr = lCurr.next;
rCurr = rCurr.next;
}
// recover right part of List

return true;
}

ListNode prev = null;
}

return prev;
}
}


### C++

class Solution {
public:

// find middle
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

// skip mid node if the number of ListNode is odd
if (fast) slow = slow->next;

// reverse right part of List
while (rCurr) {
if (rCurr->val != lCurr->val) {
return false;
}
lCurr = lCurr->next;
rCurr = rCurr->next;
}
// recover right part of List

return true;
}

ListNode* prev = NULL;
}
return prev;
}
}


## 题解3 - 递归(TLE)

### Python

class Solution:
return result[1]

def helper(self, right, result):
if right:
self.helper(right.next, result)
is_pal =  result[0].val == right.val and result[1]
result = [result[0].next, is_pal]


### Java

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

class Result {
ListNode lNode;
boolean isP;
Result(ListNode node, boolean isP) {
this.lNode = node;
this.isP = isP;
}
}

public class Solution {
/**
* @return a boolean
*/
Result result = new Result(head, true);

return result.isP;
}

private void helper(ListNode right, Result result) {
if (right != null) {
helper(right.next, result);
boolean equal = (result.lNode.val == right.val);
result.isP = equal && result.isP;
result.lNode = result.lNode.next;
}
}
}


### Bonus - Fancy Python Solution

class Solution:
nodes = []
return nodes == nodes[::-1]