Check whether a linked list is a palindrome in Java

Problem

Given a singly linked list, write a method which can tell if the integers in the list form a palindrome. As a reminder, a palindrome is a word which reads the same from left to right and from right to left. For example, the list [1,5,3,5,1] is a palindrome, but [1,8,3,8,3,1,6] is not.

A constraint to the problem is to do it in O(n) time and O(1) space

Algorithm

Since linked lists can only be read from the head to the tail, it is not possible to use the standard technique which consists on comparing values one by one while reading from both ends. Moreover, the constraint of using O(1) space prevents us from copying the linked list into a more friendly data structure like an ArrayList.

The solution proposed below consists in 3 steps. First, we need to find the middle of the list. Once the middle of the list is found, we need to split the original list in two and reverse one of the two halves. Finally, we can go through both lists and compare them element by element.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

public class Solution { public boolean isPalindrome(ListNode head) { // Return true if the list has zero or one element. if (head == null || head.next == null) { return true; } // Use two pointers to find the middle of the list. // The fast pointer goes twice faster than the slow one. ListNode fast = head; ListNode slow = head; // After the loop, the fast pointer has reached the end, // while the slow pointer is at the middle element. while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } // The second half of the list starts at slow. // We reverse it using two pointers and a // temporary variable. ListNode previous = null; ListNode current = slow; while (current != null) { ListNode temp = current.next; current.next = previous; previous = current; current = temp; } // After reversal, the variable previous points // to the head of the reversed second half's list. // Compare the first half with the second half. ListNode firstHalf = head; ListNode secondHalf = previous; while (secondHalf != null) { if (firstHalf.val != secondHalf.val) { return false; } firstHalf = firstHalf.next; secondHalf = secondHalf.next; } return true; } }

This problem can be found on leetcode and career cup.