Problem
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up: Could you do it in O(n) time and O(1) space?
Solution (Java)
/**
* 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) {
int len = 0;
ListNode right = head;
// Culculate 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;
}
}
Solution (Javascript)
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
var left = null;
var right = null;
var slow = head;
var fast = head;
var tmp = null;
while (fast && fast.next) {
fast = fast.next.next;
tmp = slow.next;
slow.next = left;
left = slow;
slow = tmp;
}
right = fast ? slow.next : slow;
while (left && right) {
if (left.val !== right.val) return false;
left = left.next;
right = right.next;
}
return true;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).