# Question

Formatted question description: https://leetcode.ca/all/234.html

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true


Example 2:

Input: head = [1,2]
Output: false


Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

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

# Algorithm

The principle of using fast and slow pointers to find the midpoint,each time the fast pointer moves two steps and the slow pointer moves one step. When the fast pointer finishes, the position of the slow pointer is the midpoint.

After finding the midpoint, flip the linked list in the second half to compare in the order of palindrome.

# Code

• 
public class Palindrome_Linked_List {

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public boolean isPalindrome(ListNode head) {

if (head == null) {
return false;
}

// 2 pointers to find mid
ListNode slowPrev = new ListNode(0);
ListNode slow = head;
ListNode fast = head;

while (fast != null && fast.next != null) {
fast = fast.next.next;

slowPrev = slow;
slow = slow.next;
}

// now slow aat middle
slowPrev.next = null; // cut

ListNode reversed2ndHalf = reverseNodeList(slow);
ListNode p1 = head;
ListNode p2 = reversed2ndHalf;

while (p1 != null && p2 != null) {
if (p1.val != p2.val) {
return false;
}

p1 = p1.next;
p2 = p2.next;
}

return true;
}

private ListNode reverseNodeList(ListNode head) {

ListNode dummy = new ListNode(0);

ListNode current = head;

while (current != null) {
ListNode currenHead = dummy.next;
ListNode nextHead = current.next;

current.next = null; // cut current node out

dummy.next = current;
current.next = currenHead;
current = nextHead;
}

return dummy.next;
}
}

############

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode cur = slow.next;
slow.next = null;
ListNode pre = null;
while (cur != null) {
ListNode t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
while (pre != null) {
if (pre.val != head.val) {
return false;
}
pre = pre.next;
head = head.next;
}
return true;
}
}

• // OJ: https://leetcode.com/problems/palindrome-linked-list/
// Time: O(N)
// Space: O(1)
class Solution {
private:
int getLength(ListNode *head) {
int len = 0;
for (; head; head = head->next, ++len);
return len;
}
ListNode *reverse(ListNode *head) {
ListNode dummy(0);
while (head) {
ListNode *node = head;
head = head->next;
node->next = dummy.next;
dummy.next = node;
}
return dummy.next;
}
public:
bool isPalindrome(ListNode* head) {
if (!head) return true;
int len = (getLength(head) + 1) / 2;
ListNode *p = head, *q;
while (--len > 0) p = p->next;
q = p->next;
p->next = NULL;
q = reverse(q);
while (head && q) {
if (head->val != q->val) return false;
head = head->next;
q = q->next;
}
return true;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
pre, cur = None, slow.next
while cur:
t = cur.next
cur.next = pre
pre, cur = cur, t
while pre:
if pre.val != head.val:
return False
pre, head = pre.next, head.next
return True

############

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

class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""

def reverseList(root):
pre = None
cur = root
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre

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

newHead = reverseList(slow)
p1 = head
p2 = newHead
while p1 and p2:
if p1.val != p2.val:
return False
p1 = p1.next
p2 = p2.next
return True


• /**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
var pre *ListNode
cur := slow.Next
for cur != nil {
t := cur.Next
cur.Next = pre
pre = cur
cur = t
}
for pre != nil {
if pre.Val != head.Val {
return false
}
pre, head = pre.Next, head.Next
}
return true
}

• /**
* Definition for singly-linked list.
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function isPalindrome(head: ListNode | null): boolean {
let slow: ListNode = head,
fast: ListNode = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
let cur: ListNode = slow.next;
slow.next = null;
let prev: ListNode = null;
while (cur != null) {
let t: ListNode = cur.next;
cur.next = prev;
prev = cur;
cur = t;
}
while (prev != null) {
if (prev.val != head.val) return false;
prev = prev.next;
head = head.next;
}
return true;
}


• /**
* Definition for singly-linked list.
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
let slow = head;
let fast = head.next;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let cur = slow.next;
slow.next = null;
let pre = null;
while (cur) {
let t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
while (pre) {
if (pre.val !== head.val) {
return false;
}
pre = pre.next;
head = head.next;
}
return true;
};


• /**
* Definition for singly-linked list.
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public bool IsPalindrome(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode cur = slow.next;
slow.next = null;
ListNode pre = null;
while (cur != null) {
ListNode t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
while (pre != null) {
if (pre.val != head.val) {
return false;
}
pre = pre.next;
head = head.next;
}
return true;
}
}