Check If Linked List Is Palindrome
You are given a Singly Linked List of integers. You have to find if the given linked list is palindrome or not.

A List is a palindrome if it reads the same from the left to the right and from the right to the left.

For example, the lists (1 - 2 - 1), (3 - 4 - 4- 3), and (1) are palindromes, while the lists (1 - 2 - 3) and (3 - 4) are not.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first and only line of each test case contains the elements of the linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case, print “True” if the given linked list is a palindrome, else print “False”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Check If Linked List Is Palindrome

You are given a Singly Linked List of integers. You have to find if the given linked list is palindrome or not.

A List is a palindrome if it reads the same from the left to the right and from the right to the left.

For example, the lists (1 -> 2 -> 1), (3 -> 4 -> 4-> 3), and (1) are palindromes, while the lists (1 -> 2 -> 3) and (3 -> 4) are not.

Input Format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first and only line of each test case contains the elements of the linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case, print “True” if the given linked list is a palindrome, else print “False”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 5 * 10^4
-10^9 <= data <= 10^9 and data != -1

Where N is the number of nodes in the linked list and ‘data’ represents the value of the nodes of the list.

Time Limit: 1sec

Accepted Answer

A simple approach could be to use a stack. Traverse the given list and push all the nodes to a stack. Now, Traverse the list again. For every visited node, pop the topmost node from the stack and compare data of popped node with the currently visited node. If all nodes match, then the linked list is a palindrome.
Time Complexity :O(N)
Auxiliary Space: O(N)
A better approach would be to reverse the second half of the list. Get the middle of the linked list and reverse the second half of the linked list.
Next, Check if the first half and second half are identical. If they are identical, return true.
Time Complexity :O(N)
Auxiliary Space: O(1)

Accepted Answer

Using Stack

The idea is to store the list values in a stack and then compare the values in the list with the values in the stack.

Algorithm:

Traverse the list from head to tail and push every node in the stack.
Make a pointer ‘cur’ which initially points to the head node.
If value at ‘cur’ is not equal to the top element of the stack, then the given list is not a palindrome
Else, move the ‘cur’ pointer to its next node and pop the top element from the stack.
If stack is empty, then the given list is a palindrome
Else, repeat the steps 3 to 6.

Space Complexity: O(n)Explanation:

O(N), Where N is the number of nodes in the linked list.

We are storing node values in a stack which will take O(N) extra space.

Time Complexity: O(n)Explanation:

O(N), Where N is the number of nodes in the linked list.

We are traversing the list twice and traversing a list takes O(N) time, thus the final time complexity is O(2 * N) = O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space complexity: O(N)

    

    Where 'N' is the number of nodes in the linked list

*/



import java.util.Stack;



public class Solution 

{

    public static boolean isPalindrome(Node head) 

    {

        

        Stack visitedNodes = new Stack<>();



        // Push all nodes in the stack

        Node cur = head;

        while (cur != null)

        {

            visitedNodes.push(cur);

            cur = cur.next;

        }

    

        cur = head;

        while (cur != null)

        {

            // Compare node values

            Node temp = visitedNodes.peek();

            if (cur.data != temp.data)

            {

                return false;

            }

            visitedNodes.pop();

            cur = cur.next;

        }

    

        return true;

    }

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space complexity: O(N)

    

    Where N is the number of nodes in the linked list.

'''





def isPalindrome(head):



    visitedNodes = []



    # push all nodes in the stack

    cur = head



    while (cur != None):

        visitedNodes.append(cur)

        cur = cur.next



    cur = head

    while (cur != None):



        # compare node values

        temp = visitedNodes.pop()

        if (cur.data != temp.data):

            return False



        cur = cur.next



    return True

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space complexity: O(N)
    
    Where N is the number of nodes in the linked list.
*/

#include 

bool isPalindrome(Node *head)
{
    stack visitedNodes;
    // push all nodes in the stack
    Node *cur = head;
    while (cur != NULL)
    {
        visitedNodes.push(cur);
        cur = cur->next;
    }

    cur = head;
    while (cur != NULL)
    {
        // compare node values
        Node *temp = visitedNodes.top();
        if (cur->data != temp->data)
        {
            return false;
        }
        visitedNodes.pop();
        cur = cur->next;
    }

    return true;
}

Accepted Answer

Recursive Approach

Approach:

The idea is to reach the end of the list and then compare if the last node has the same value as the first node, the second last node has the same value as the second node and so on..

For comparing node values we will use a the recursion stack.

For example, if the given list is (1 -> 2 -> 3 -> 2 -> 1).

First we will traverse the list upto last node. Now, when we are coming out of the Nth recursive state, list (1 -> 2 -> 3 -> 2 -> 1) will be present in the recursive stack with the right node being 1 (Nth node), when we are coming out of the (N-1)th recursive state, list (1 -> 2 -> 3 -> 2 -> 1) will be present in the recursive stack with the right node being 2 ((N-1)th node), and so on…

So, when we are coming out of Nth recursive state, we will compare Nth node with 1st node,when we are coming out of (N-1)th recursive state, we will compare (N-1)th node with 2nd node,... when we are coming out of 2nd recursive state, we will compare 2nd node with (N-1)th node, when we are coming out of 1st recursive state, we will compare 1st node with Nth node.

If all these states return true, then the list is a palindrome.

Algorithm:

Make a recursive function isPalindromeHelper(left, right) {pass left pointer by its reference}, this function checks whether the list between left and right is palindrome or not.

Call the function: isPalindromeHelper(head, head).
Base case: if right is equal to NULL, return true
Call the next recursive state: isPalindromeHelper(left, right->next).
If the sub-list is not palindrome or the value at ‘left’ node is not equal to ‘right’ node, return false.
Else, move the ‘left’ pointer to its next node and return true from the current recursive state.

Space Complexity: O(n)Explanation:

O(N), Where N is the number of nodes in the linked list.

O(N) recursion stack space will be used.

Time Complexity: O(n)Explanation:

O(N), Where N is the number of nodes in the linked list.

We traverse every node in the list only once, thus the final time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space complexity: O(N)

    

    Where 'N' is the number of nodes in the linked list.

*/



public class Solution 

{

    public static Node tempHead;

    public static Node left;



    public static boolean isPalindromeHelper(Node right) 

    {

        left = tempHead;



        // Base case

        if (right == null) 

        {

            return true;

        }



        boolean isSublistPalindrome = isPalindromeHelper(right.next);

        if (isSublistPalindrome == false) 

        {

            return false;

        }



        if (left.data != right.data) 

        {

            return false;

        }



        // Move left pointer to its next node

        left = left.next;

        return true;

    }



    public static boolean isPalindrome(Node head) 

    {

        // Call the recursive function

        tempHead = head;

        return isPalindromeHelper(head);

    }

}

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space complexity: O(N)
    
    Where N is the number of nodes in the linked list.
*/

bool isPalindromeHelper(Node **left, Node *right)
{
    // base case
    if (right == NULL)
    {
        return true;
    }

    bool isSublistPalindrome = isPalindromeHelper(left, right->next);
    if (isSublistPalindrome == false)
    {
        return false;
    }

    if ((*left)->data != right->data)
    {
        return false;
    }

    // move left pointer to its next node
    *left = (*left)->next;
    return true;
}

bool isPalindrome(Node *head)
{
    // call the recursive function
    return isPalindromeHelper(&head, head);
}

Accepted Answer

Dividing into two sub-lists

The idea is to divide the list into two halves from mid and reverse the second half. If both halves are equal then the given list is palindrome.

Divide the list into two lists ‘first’ and ‘second’.
- Make two pointers ‘slow’ and ‘fast’ which initially points to the head node.
- Move ‘slow’ and ‘fast’ pointer as follows until ‘fast’ becomes NULL:
  - slow = slow->next
  - fast = fast->next->next
- ‘First’ list will contain nodes from head to previous node of ‘slow’.
- ‘Second’ list will contain nodes from slow to ‘tail’ of the given list.
- Reverse the ‘second’ list.
Now, traverse the two lists and compare node values (if the number of nodes in the given list is odd, then the ‘second’ list will contain one node more than the ‘first’ list, for this we can neglect the last node of the ‘second’ list).

Space Complexity: O(1)Explanation:

O(1)

Constant additional space is required.

Time Complexity: O(n)Explanation:

O(N), Where N is the number of nodes in the linked list.

We are traversing the list multiple times and traversing a list takes O(N) time. Also, reversing a list takes O(K) time, where K is the number of nodes in the list. Since we are reversing the second list, the time complexity of reversal will be O(N / 2) = O(N) (as there will be N/2 nodes in the second list). Thus, the final time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space complexity: O(1)

    

    Where N is the number of nodes in the linked list.

*/



public class Solution 

{

    public static boolean isPalindrome(Node head) 

    {

        // If list contains only one node

        if (head.next == null) 

        {

            return true;

        }



        // Dividing list into two sublists

        Node slow = head, fast = head, prev = null;

        while (fast != null && fast.next != null) 

        {

            prev = slow;

            slow = slow.next;

            fast = fast.next.next;

        }



        // First list

        Node first = head;

        prev.next = null;



        // Second list

        Node second = slow;



        // Reverse the second list

        prev = null;

        while (second != null) 

        {

            Node temp = second.next;

            second.next = prev;

            prev = second;

            second = temp;

        }



        second = prev;



        // Compare the two lists

        while (first != null) 

        {

            if (first.data != second.data) 

            {

                return false;

            }

            first = first.next;

            second = second.next;

        }

        return true;

    }

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space complexity: O(1)

    

    Where N is the number of nodes in the linked list.

'''





def isPalindrome(head):



    # if list contains only one node

    if (head.next == None):

        return True



    # dividing list into two sublists



    slow, fast, prev = head, head, None

    while (fast != None and fast.next != None):



        prev = slow

        slow = slow.next

        fast = fast.next.next



    # first list

    first = head

    prev.next = None



    # second list

    second = slow



    # reverse the second list

    prev = None

    while (second != None):



        temp = second.next

        second.next = prev

        prev = second

        second = temp



    second = prev



    # compare the two lists

    while (first != None):



        if (first.data != second.data):

            return False



        first = first.next

        second = second.next



    return True

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space complexity: O(1)
    
    Where N is the number of nodes in the linked list.
*/

bool isPalindrome(Node *head)
{
    // if list contains only one node
    if (head->next == NULL)
    {
        return true;
    }

    // dividing list into two sublists

    Node *slow = head, *fast = head, *prev = NULL;
    while (fast != NULL && fast->next != NULL)
    {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    // first list
    Node *first = head;
    prev->next = NULL;
    // second list
    Node *second = slow;

    // reverse the second list
    prev = NULL;
    while (second != NULL)
    {
        Node *temp = second->next;
        second->next = prev;
        prev = second;
        second = temp;
    }
    second = prev;

    // compare the two lists
    while (first != NULL)
    {
        if (first->data != second->data)
        {
            return false;
        }
        first = first->next;
        second = second->next;
    }

    return true;
}

You are given a Singly Linked List of integers. You have to find if the given linked list is palindrome or not.

A List is a palindrome if it reads the same from the left to the right and from the right to the left.

For example, the lists (1 -> 2 -> 1), (3 -> 4 -> 4-> 3), and (1) are palindromes, while the lists (1 -> 2 -> 3) and (3 -> 4) are not.

Input Format:

Output Format :

Note:

Constraints :

Approach:

Top Quikr Software Developer interview questions & answers

Popular interview questions of Software Developer