Palindrome Linked List

EASY

Description

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

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, 10⁵].
0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Approaches

Checkout 3 different approaches to solve Palindrome Linked List. Click on different approaches to view the approach and algorithm in detail.

Convert to Array Approach

Convert the linked list to an array and use two pointers to check if it's a palindrome.

Algorithm

Create an ArrayList to store the values
Traverse the linked list and add all values to the ArrayList
Use two pointers (left and right) starting from the beginning and end of the ArrayList
Compare values at left and right pointers
Move left pointer forward and right pointer backward
If any values don't match, return false
If all values match, return true

This approach involves converting the linked list to an array first, then using two pointers (one from start and one from end) to check if the values match. While this is the most straightforward solution, it requires extra space to store the array.

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<>();
        
        // Convert linked list to array
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }
        
        // Use two pointers to check palindrome
        int left = 0;
        int right = values.size() - 1;
        while (left < right) {
            if (!values.get(left).equals(values.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}```

Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the linked listSpace Complexity: O(n) to store the array of values

Pros and Cons

Pros:

Easy to implement and understand
Good for interviews when asked to provide a quick solution
Can handle null and single node cases easily

Cons:

Uses extra space to store the array
Not the most efficient solution in terms of space complexity
Requires two passes through the data

Code Solutions

Checking out 5 solutions in different languages for Palindrome Linked List. Click on different languages to view the code.

/** * 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 ) { ListNode slow = head ; ListNode fast = head . next ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } ListNode cur = slow . next ; slow . next = null ; ListNode pre = null ; while ( cur != null ) { ListNode t = cur . next ; cur . next = pre ; pre = cur ; cur = t ; } while ( pre != null ) { if ( pre . val != head . val ) { return false ; } pre = pre . next ; head = head . next ; } return true ; } }

Video Solution

Watch the video walkthrough for Palindrome Linked List

Patterns:

RecursionTwo Pointers

Data Structures:

Linked ListStack

Companies:

Barclays |Devsinc |Intuit |Morgan Stanley |