Given a singly linked list, determine if it is a palindrome.
GeeksforGeeks
YouTube
Input: 1->2
Output: false
Input: 1->2->2->1
Output: true
Could you do it in O(n) time and O(1) space?
Last updated
Was this helpful?
Was this helpful?
// 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;
}
}/**
* Time complexity : O(n)
* Space complexity : O(n)
*/
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<>();
// Convert LinkedList into ArrayList.
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// Use two-pointer technique to check for palindrome.
int front = 0;
int back = vals.size() - 1;
while (front < back) {
// Note that we must use ! .equals instead of !=
// because we are comparing Integer, not int.
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}/**
* Time complexity : O(n)
* Space complexity : O(1)
*/
class Solution {
private ListNode left;
public boolean isPalindrome(ListNode head) {
left = head;
return isPalindromeHelper(head);
}
private boolean isPalindromeHelper(ListNode right) {
if(right == null) {
return true;
}
boolean tmp = isPalindromeHelper(right.next);
if(!tmp) {
return false;
}
boolean result = (left.val == right.val);
left = left.next;
return result;
}
}/**
* Time complexity : O(n)
* Space complexity : O(1)
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) return true;
// Find the end of first half and reverse second half.
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// Check whether or not there is a palindrome.
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) result = false;
p1 = p1.next;
p2 = p2.next;
}
// Restore the list and return the result.
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
// Taken from https://leetcode.com/problems/reverse-linked-list/solution/
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}