Problem

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

Examples

Example 1:

1
2
3
4

Input: head = [1,2,2,1]
Output: true

head = 1 -> 2 -> 2 -> 1

Example 2:

1
2
3
4

Input: head = [1,2]
Output: true

head = 1 -> 2

Solution

Method 1 - Using Array to Store Linked List

We can store values from linked list in an array. Then the problem becomes - Check if given array is Palindrome OR Not

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public boolean isPalindrome(ListNode head) {
    if(head == null)
        return true;
	List<Integer> arrList = new ArrayList<>();
	ListNode p = head;
    while(p != null){
	    arrList.add(p.val);
        p = p.next;
    }
 
    return isPalindrome(
	    arrList.stream().mapToInt(i -> i).toArray());
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Create new reversed list and compare

We can create a new list in reversed order and then compare each node. Here is the Reverse Linked List.

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

public boolean isPalindrome(ListNode head) {
    if(head == null)
        return true;
 
    ListNode p = head;
    ListNode prev = new ListNode(head.val);
 
    while(p.next != null){
        ListNode temp = new ListNode(p.next.val);
        temp.next = prev;
        prev = temp;
        p = p.next;
    }
 
    ListNode p1 = head;
    ListNode p2 = prev;
 
    while(p1!=null){
        if(p1.val != p2.val){
            return false;}
 
        p1 = p1.next;
        p2 = p2.next;
    }
 
    return true;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Break and Reverse Second Half 🏆

We can use a fast and slow pointer to get the center of the list, then reverse the second list and compare two sublists.

  1. Get the middle of the linked list
  2. Reverse the second half of the linked list.
  3. Compare the first half and second half.
  4. Construct the original linked list by reversing the second half again and attaching it back to the first half.

Downside of the approach is we are changing our DS.

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

public boolean isPalindrome(ListNode head) {
 
    if(head == null || head.next==null)
        return true;
 
    //find list middle = slow pointer
    ListNode fast = head;
    ListNode slow = head;
 
    while(fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
    }
 
    //reverse second part of the list
    ListNode prev = null;
 
    while(slow!=null){
        ListNode nxt = slow.next;
        slow.next = prev;
        prev = slow;
        slow = nxt;
    }

	// Check palindrome 
    ListNode left = head, right = prev;
	// we are using right as for odd numbered list
	// right side will be smaller
    while(right!=null){
        if(left.val != right.val)
            return false;
 
        left = left.next;
        right = right.next;
 
    }
 
    return true;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 4 - Recursive 🏆

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

public class Solution {
    ListNode left;
 
    public boolean isPalindrome(ListNode head) {
        left = head;
 
        boolean result = helper(head);
        return result;
    }
 
    public boolean helper(ListNode right){
 
        //stop recursion
        if (right == null)
            return true;
 
        //if sub-list is not palindrome,  return false
        boolean x = helper(right.next);
        if (!x)
            return false;
 
        //current left and right
        boolean y = (left.val == right.val);
 
        //move left to next
        left = left.next;
 
        return y;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)