LeetCode-in-All
234. Palindrome Linked List
Easy
Given the head of a singly linked list, return true if it is a palindrome.
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?
Solution
using LeetCodeNet.Com_github_leetcode;
/**
* 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) {
int len = 0;
ListNode right = head;
// Calculate the length
while (right != null) {
right = right.next;
len++;
}
// Reverse the right half of the list
len = len / 2;
right = head;
for (int i = 0; i < len; i++) {
right = right.next;
}
ListNode prev = null;
while (right != null) {
ListNode next = right.next;
right.next = prev;
prev = right;
right = next;
}
// Compare left half and right half
for (int i = 0; i < len; i++) {
if (prev != null && head.val == prev.val) {
head = head.next;
prev = prev.next;
} else {
return false;
}
}
return true;
}
}