Palindrome Linked List Leetcode Solution  

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Capital One Cisco Facebook Google Grab Intel IXL Microsoft Nutanix Oracle Paytm Snapchat Uber Yandex
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Linked-List Two Pointers

In the problem “Palindrome Linked List”, we have to check whether a given singly integer linked list is a palindrome or not.

Example  

List = {1 -> 2 -> 3 -> 2 -> 1}
true

Explanation #1: The list is palindrome as all elements from the start and back are the same in value.

List = {1 -> 2 -> 3 -> 4 -> 5}
false

Explanation #2: The list is not palindrome as elements from back and forth are not the same.

Approach(Recursion 

This is easy to notice that we need to have the details of the nodes from the back of the array for checking palindrome properties. In this case, we have a singly linked list meaning that we can only iterate forward to reach any node. Thus, it becomes important to use some data structure to hold the nodes from the back, e.g. stack is a possible option as it keeps the most recent node at the top. We can also use recursion similarly. Recursion is an elegant to get the node values in reverse order. Consider the below general pseudocode for better understanding:

Please click Like if you loved this article?

inorderTraversal(root)
{
    if(root == null)
        return;
    inorderTraversal(root.left);
    print(root.data);
    inorderTraversal(root.right);
}

The above code first prints left nodes in the tree because we recursively call the function to go to left children of any root before printing the value of the node itself. Similarly, we can use recursion to go to the last nodes first and when the function will backtrack, we will be getting the node values in reverse order. We will use a variable to iterate forward which will be unaffected by recursion. In this way, we can compare forward iterator’s value and reverse node’s value obtained by recursion to compare elements.

See also
Number of Steps to Reduce a Number to Zero Leetcode Solution

Algorithm

  1. A function isPalindrome() is used to return whether a list with head is palindrome or not
  2. We declare a data member of the class named front to store nodes for forward iterations
  3. In isPalindrom():
    • Initialize front = head
    • return palindromeCheck(head)
  4. In palindromeCheck(current):
    • If current is null:
      • return true
    • If palindromeCheck(current.next) is false:
      • return false
    • If current.value is not equal to front.value
      • return false
    • increment front as:
      • front = front.next
    • return true as we performed all the checks
  5. Print the result

Implementation of Palindrome Linked List Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

bool palindromeCheck(listNode* head)
{
    if(head == NULL)
        return true;
    if(!palindromeCheck(head->next))
        return false;
    if(front->value != head->value)
        return false;
    front = front->next;
    return true;
}

bool isPalindrome(listNode* head)
{
    front = head;
    return palindromeCheck(head);
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Java Program

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    static listNode front;
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static boolean palindromeCheck(listNode head)
    {
        if(head == null)
            return true;
        if(!palindromeCheck(head.next))
            return false;
        if(front.value != head.value)
            return false;
        front = front.next;
        return true;
    }

    static boolean isPalindrome(listNode head)
    {
        front = head;
        return palindromeCheck(head);
    }
}
true

Complexity Analysis of Palindrome Linked List Leetcode Solution

Time Complexity

O(N) as we traverse the list once using recursion. Here, N = number of nodes in the list.

See also
Kth Missing Positive Number Leetcode Solution

Space Complexity

O(N) as we call a recursive function to check for every node creating N stack frames in the memory.

Approach(Reverse Other Half)  

The only way to get rid of the space used in recursion is to modify the given list in-place. We reverse the second half of the linked list and then use two forward iterators for both halves to check if corresponding values are equal. For this process, we need to:

  • find the middle of the list so that we can reverse the second half.
  • create a function to reverse the second half of the list
  • check if the first and second half are equal

All of the above can be done in linear time. After we reverse the linked list, we start checking till the second half gets completed.

Palindrome Linked List Leetcode SolutionPin

Algorithm

  1. If head is null:
    • return true
  2. Find the middle of the linked list using middleOfList(headfunction:
    • Initialize two pointers slow and fast both pointing to the head of the list
    • Until fast.next and fast.next.next are both not null:
      1. Increment slow by 1, slow = slow.next
      2. Increment fast by 2, fast = fast.next.next
    • slow pointer now points to the middle of the list
    • return slow
  3. Now we reverse the second half of the list calling reverseList(head = middle.next) function
    • Initialise prev = null
    • while head is not null:
      • Store next node in a temporary variable, as next
      • Reverse the pointer direction by using head.next = prev
      • prev = head
      • Move ahead in the list using head = next
    • return prev
  4. Now, intialise two pointers ptr1 and ptr2 to iterate through both halves:
    1. ptr1 = head
    2. ptr2 = start of second half
    3. while ptr2 is not null:
      1. if ptr1.value is not equal to ptr2.value
        1. return false
    4. return true as we checked every node in the first and second half
  5. Print the result
See also
Construct BST from given Preorder Traversal

Implementation of Palindrome Linked List Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};

listNode* middleOfList(listNode* head)
{
    listNode *slow = head , *fast = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

listNode* reverseList(listNode* head)
{
    listNode *prev = NULL;
    while(head != NULL)
    {
        listNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

bool isPalindrome(listNode* head)
{
    if(head == NULL)
        return true;
    listNode* middleNode = middleOfList(head);
    listNode* startOfSecondHalf = reverseList(middleNode->next);

    listNode *ptr1 = head , *ptr2 = startOfSecondHalf;
    while(ptr2 != NULL)
    {
        if(ptr1->value != ptr2->value)
            return false;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return true;
}

int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);
    head->next->next->next = new listNode(2);
    head->next->next->next->next = new listNode(1);

    cout << (isPalindrome(head) ? "true\n" : "false\n");
    return 0;
}

Java Program

class listNode
{
    int value;
    listNode next;
    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class palindrome_linked_list
{
    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(2);
        head.next.next.next.next = new listNode(1);

        System.out.println((isPalindrome(head)) ? "true" : "false");
    }

    static listNode middleOfList(listNode head)
    {
        listNode slow = head , fast = head;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static listNode reverseList(listNode head)
    {
        listNode prev = null;
        while(head != null)
        {
            listNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    static boolean isPalindrome(listNode head)
    {
        if(head == null)
            return true;
        listNode middleNode = middleOfList(head);
        listNode startOfSecondHalf = reverseList(middleNode.next);

        listNode ptr1 = head , ptr2 = startOfSecondHalf;
        while(ptr2 != null)
        {
            if(ptr1.value != ptr2.value)
                return false;
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return true;
    }
}
true

Complexity Analysis of Palindrome Linked List Leetcode Solution

Time Complexity

O(N) as we use linear loops to find the middle of the list, reverse it, and compare both the halves. Here, N = size of the list.

See also
Best Time to Buy and Sell Stock

Space Complexity

O(1) as we use only constant extra space.

Please click Like if you loved this article?

1