234. Palindrome Linked List

Description

Given a singly linked list, determine if it is a palindrome.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 1->2

Output: false

Example 2

Input: 1->2->2->1

Output: true

Solutions

ListNode

// 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;
		}
}

Solution 1

/**
 * 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;
    }
}

Solution 2

/**
 * 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;
    }
}

Solution 3

/**
 * 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;
    }
}

Follow up

• Could you do it in O(n) time and O(1) space?