Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Palindrome Linked List

Easy
0/40
Average time to solve is 20m
profile
Contributed by
175 upvotes
Asked in companies
CiscoMicrosoftAmazon

Problem statement

You are given a singly Linked List of integers. Your task is to return true if the given singly linked list is a palindrome otherwise returns false.

For example:
The given linked list is 1 -> 2 -> 3 -> 2-> 1-> NULL.

It is a palindrome linked list because the given linked list has the same order of elements when traversed forwards and backward​.
Follow Up:
Can you solve the problem in O(N) time complexity and O(1) space complexity iteratively?
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.

The only line of each test case contains the elements of the singly 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” or “false” in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
0 <= L <= 10^5
1 <= data <= 10^9 and data != -1

Where L is the number of nodes in the Linked List.

Time Limit: 1 sec
Sample Input 1 :
2
1 2 3 4 5 6 -1
1 2 1 -1
Sample Output 1 :
false
true
Explanation for sample 1:
For the first test case, it is not a palindrome because Linked List doesn't have the same order of elements when traversed forwards and backwards​.

For the second test case, it is a palindrome linked list because a Linked List has the same order of elements when traversed forwards and backwards​.
Sample Input 2 :
2
1 -1
1 10 45 10 1 -1
Sample Output 2 :
true
true
Hint

Think of a solution to store Linked List elements in a data structure that gives reverse order of the linked list.

Approaches (4)
Using Stack
  1. The idea is to traverse the Linked List from head to tail and push every encountered node data into the stack.
  2. Then we traverse the Linked List and for each node, we pop the top element from the stack and compare it with current node data of the Linked List. If they mismatch then the current linked list is not palindrome else if all elements match then the linked list is a palindrome.
Time Complexity

O(N), where N is the number of nodes in the Linked List.

 

In the worst case, we are traversing the whole linked list two times i.e O(N). Hence, the overall complexity is O(N).

Space Complexity

O(N), where N is the total number of nodes in the Linked List.

 

In the worst case, we are storing the all Linked List node value in the stack. Hence, overall complexity will be O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Palindrome Linked List
All tags
Sort by
Search icon

Interview problems

can anyone told me that where I mistaken. here 3 test case is passes but then i got error.

import java.util.*;

 

public class Solution {

    public static LinkedListNode<Integer> midNode(LinkedListNode<Integer> head) {

        LinkedListNode<Integer> slow = head;

        LinkedListNode<Integer> fast = head;

 

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

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

 

    public static boolean isPalindrome(LinkedListNode<Integer> head) {

        if (head == null || head.next == null) {

            return true;

        }

 

        LinkedListNode<Integer> midNode = midNode(head);

        LinkedListNode<Integer> prev = null;

        LinkedListNode<Integer> curr = midNode;

        LinkedListNode<Integer> next;

 

        while (curr != null) {

            next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;

        }

 

        LinkedListNode<Integer> left = head;

        LinkedListNode<Integer> right = prev;

 

        while (right != null) {

            if (left.data != right.data) {

                return false;

            }

            left = left.next;

            right = right.next;

        }

        return true;

    }

}

63 views
1 reply
0 upvotes
profile

Interview problems

Palindrome Linked List (using Stack) in C++

bool isPalindrome(LinkedListNode<int> *head) {

    // Write your code here.

    LinkedListNode<int> *temp;

    temp=head;

    stack<int> st;

    while(temp!=NULL){

        st.push(temp->data);

        temp=temp->next;

    }

    temp=head;

    while(temp!=NULL){

        if(temp->data != st.top())

         return false;

        temp=temp->next;

        st.pop();

    }

    return true;

 

}

338 views
0 replies
0 upvotes

Interview problems

Palindrome Linked List

bool isPalindrome(LinkedListNode<int> *head) {

    // Write your code here.

    if(head == NULL || head->next == NULL){

        return true;

    }

    LinkedListNode<int>* n1=head;

    vector<int> arr;

    while(n1 != NULL){

        arr.push_back(n1->data);

        n1 = n1->next;

    }

    int i=0;

    int j = arr.size()-1;

    while(i<=j){

        if (arr[i] != arr[j]) {

            return false;

        }

        i++;

        j--;

    }

    return true;

}

243 views
0 replies
0 upvotes

Interview problems

Easy c++ optimized solution in O(1) space

LinkedListNode<int>* getmid(LinkedListNode<int>* &head){

    LinkedListNode<int>* slow = head;

    LinkedListNode<int>* fast = head->next;

    while(fast != NULL && fast->next != NULL){

        fast = fast->next->next;

        slow = slow->next;

    }

    return slow;

}

 

LinkedListNode<int>* reverse(LinkedListNode<int>* &head){

    LinkedListNode<int>* prev = NULL;

    LinkedListNode<int>* curr = head;

    while(curr != NULL){

        LinkedListNode<int>* next1 = curr->next;

        curr->next = prev;

        prev = curr;

        curr = next1;

    }

    return prev;

}

 

bool isPalindrome(LinkedListNode<int> *head) {

    // edge case

    if(head == NULL || head->next == NULL)      return 1;

 

    // pointer

    LinkedListNode<int>* temp = head;

 

    // step 1:  mid find

    LinkedListNode<int>* mid = getmid(head);

 

    // step2 : reverse after mid

    LinkedListNode<int>* rev = reverse(mid->next);

 

    // step 3: compare

    while(rev != NULL){

        if(temp->data != rev->data){

            return 0;

        }

        rev = rev->next;

        temp = temp->next;

    }

    // arranging back

    rev = mid->next;

    reverse(rev);

    return 1;

}

309 views
0 replies
0 upvotes

Interview problems

JAVA Solution || O(n)

/* In first Loop : find the middle ,

in second Loop : reverse the LL from middle 

make two halfs   in third  Loop : compare that half */ public static boolean isPalindrome(LinkedListNode<Integer> head) {

        LinkedListNode slow = head;

        LinkedListNode fast = head;  

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

            slow = slow.next;

            fast = fast.next.next;

        }  

        LinkedListNode curr = slow;

        LinkedListNode prev = null;

        

        while(curr!= null ){

            LinkedListNode nextNode = curr.next;

            curr.next = prev;

            prev = curr;

            curr = nextNode;

        }  

        LinkedListNode firsthalf = head;

        LinkedListNode secondhalf = prev;  

        while(secondhalf!=null){

            if(!firsthalf.data.equals(secondhalf.data)){

                return false;

            }

            firsthalf = firsthalf.next;

            secondhalf= secondhalf.next;            

        }

        return true;

    }

284 views
0 replies
1 upvote

Interview problems

Palindrome LL using Stack

import java.util.* ;

import java.io.*; 

/****************************************************************

 

    Following is the class structure of the LinkedListNode class:

    

    class LinkedListNode<T> {

        T data;

        LinkedListNode<T> next;

 

        public LinkedListNode(T data) {

            this.data = data;

        }

    }

 

*****************************************************************/

 

public class Solution {

 

    public static boolean isPalindrome(LinkedListNode<Integer> head) {

        // Write your code here!

        LinkedListNode<Integer> t=head;

        Stack<Integer>st=new Stack<>();

        while(t!=null){

            st.push(t.data);

            t=t.next;

        }

        t=head;

        while(t!=null){

            if(!t.data.equals(st.pop()))return false;

            // st.pop();

            t=t.next;

        }

        return true;

    }

}

107 views
0 replies
1 upvote

Interview problems

Easy C++ || 99.5% || T.C = O(N) || S.C = O(1) || 2 Approaches || Easy Solution ||

Approach 1:

 

The checkPalindrome function takes a vector of integers (arr) as input and checks whether it's a palindrome or not. It uses two pointers, s starting from the beginning of the array and e starting from the end. It iterates through the array and compares elements at s and e. If any mismatch is found, it returns false (0). Otherwise, it continues moving s towards the end and e towards the beginning until s becomes greater than or equal to e, at which point it returns true (1).

The isPalindrome function takes a pointer to the head of a linked list (head) as input and checks whether the linked list is a palindrome or not. It initializes an empty vector arr to store the elements of the linked list. It then traverses the linked list, pushing the data of each node into the vector arr. Finally, it calls the checkPalindrome function with the vector arr as input and returns its result.

This approach converts the linked list into a vector and then checks if the vector is a palindrome, thus solving the problem.

Now, let's analyze the time and space complexity of the provided code:

Time Complexity:

  • The time complexity of the isPalindrome function is O(n), where n is the number of nodes in the linked list. This is because it iterates through the entire linked list once to create the vector arr.
  • The time complexity of the checkPalindrome function is also O(n), where n is the size of the input vector arr. This is because it iterates through the vector once to check for palindromicity.

Space Complexity:

  • The space complexity of the isPalindrome function is O(n), where n is the number of nodes in the linked list. This is because it creates a vector of size n to store the elements of the linked list.
  • The space complexity of the checkPalindrome function is O(1), as it only uses a constant amount of extra space regardless of the input size.

Overall, the time complexity of the provided code is O(n), and the space complexity is O(n), where n is the number of nodes in the linked list.

 

Code:

 

bool checkPalindrome(vector<int> arr){

 

    int n = arr.size();

    int s = 0;

    int e = n-1;

 

    while(s<=e){

        if(arr[s]!=arr[e]){

            return 0;

        }

 

        s++;

        e--;

    }

    return 1;

}

 

bool isPalindrome(LinkedListNode<int> *head) {

    // Write your code here.

 

    if(head==NULL || head->next==NULL){

        return true;

    }

 

     vector<int> arr;

 

     LinkedListNode<int>* temp = head;

     while(temp!=NULL){

         arr.push_back(temp->data);

         temp = temp->next;

     }

 

     return checkPalindrome(arr);

}

 

 

Approach 2:

 

Reversing the second half of the list: First, the mid function finds the middle node of the linked list using the slow and fast pointer technique. Then, it returns the pointer to the middle node.

After finding the middle node, the reverse function is used to reverse the second half of the linked list starting from the middle node. This function iterates through the list, reversing the links between nodes.

Once the second half is reversed, the original list is divided into two halves: head1 and head2. head1 points to the first half of the list, and head2 points to the reversed second half.

Then, a comparison is made between head1 and head2. If all corresponding elements match, the list is a palindrome; otherwise, it's not.

Finally, the function returns true if the linked list is a palindrome and false otherwise.

This approach avoids using extra space to store the elements of the linked list in an array, unlike the previous approach.

Let's analyze the time and space complexity of this approach:

Time Complexity:

  • Finding the middle node (mid function) takes O(n/2) time, where n is the number of nodes in the linked list.
  • Reversing the second half of the list (reverse function) also takes O(n/2) time.
  • The comparison between the first and second halves takes O(n/2) time.
  • Overall, the time complexity is O(n).

Space Complexity:

  • The space complexity is O(1) because the algorithm only uses a constant amount of extra space for pointers and variables, regardless of the size of the input linked list.

Therefore, this approach efficiently determines whether a linked list is a palindrome without using extra space for storing the elements of the list.

 

Code:

 

LinkedListNode<int>* reverse(LinkedListNode<int>* head){

    LinkedListNode<int>* curr = head;

    LinkedListNode<int>* prev = NULL;

    LinkedListNode<int>* next = NULL;

 

    while(curr != NULL){

        next = curr -> next;

        curr -> next = prev;

        prev = curr;

        curr = next;

    }

 

    return prev;

}

 

LinkedListNode<int>* mid(LinkedListNode<int>* head){

    LinkedListNode<int>* slow = head;

    LinkedListNode<int>* fast = head->next;

 

    while(fast!=NULL && fast->next != NULL){

        fast = fast->next->next;

        slow = slow->next;

    }

 

    return slow;

}

 

// bool checkPalindrome(vector<int> arr){

 

//     int n = arr.size();

//     int s = 0;

//     int e = n-1;

 

//     while(s<=e){

//         if(arr[s]!=arr[e]){

//             return 0;

//         }

 

//         s++;

//         e--;

//     }

//     return 1;

// }

 

bool isPalindrome(LinkedListNode<int> *head) {

    // Write your code here.

 

    if(head==NULL || head->next==NULL){

        return true;

    }

 

    // vector<int> arr;

 

    // LinkedListNode<int>* temp = head;

    // while(temp!=NULL){

    //     arr.push_back(temp->data);

    //     temp = temp->next;

    // }

 

    // return checkPalindrome(arr);

 

    LinkedListNode<int>* middle = mid(head);

 

    LinkedListNode<int>* temp = middle -> next;

    middle -> next = reverse(temp);

    

    LinkedListNode<int>* head1 = head;

    LinkedListNode<int>* head2 = middle->next;

 

    while(head2!=NULL){

        if(head1->data != head2->data){

            return false;

        }

        head1 = head1 -> next;

        head2 = head2 -> next;

    }

 

    return true;

}

 

 

239 views
0 replies
0 upvotes

Interview problems

palimdrome solution in java

public class Solution {

    public static boolean isPalindrome(LinkedListNode<Integer> head) {

        if (head == null || head.next == null) {

            return true; 

        }

 

        LinkedListNode<Integer> slow = head;

        LinkedListNode<Integer> fast = head;

        LinkedListNode<Integer> prev = null;

 

        // Find the middle of the linked list and reverse the second half

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

            fast = fast.next.next;

            LinkedListNode<Integer> next = slow.next;

            slow.next = prev;

            prev = slow;

            slow = next;

        }

 

        // If the number of nodes is odd, move slow pointer one step further

        if (fast != null) {

            slow = slow.next;

        }

 

        // Compare the first half with the reversed second half

        while (prev != null && slow != null) {

            if (!prev.data.equals(slow.data)) {

                return false; 

            }

            prev = prev.next;

            slow = slow.next;

        }

 

        return true; // Palindrome

    }

}

141 views
0 replies
0 upvotes

Interview problems

C++ || Easiest Solution || Using vector

void indata(vector<int> &lldata, LinkedListNode<int> *head){

    

    while(head != NULL){

        lldata.push_back(head -> data);

        head = head -> next;

    }

}

bool isPalindrome(LinkedListNode<int> *head) {

 

    if(head == NULL) return true;

 

    vector<int> lldata;

    indata(lldata, head);

 

    for(int i = lldata.size() - 1; i >= 0; i--){

        if(lldata[i] != head -> data) return false;

        head = head -> next;

    }

    return true;

}

140 views
0 replies
0 upvotes

Interview problems

Easy C++ Solution

 

LinkedListNode<int>* reverse(LinkedListNode<int> *head){

    LinkedListNode<int> *prev = NULL;

    LinkedListNode<int> *curr = head;

    LinkedListNode<int> *forward = NULL;

    while(curr != NULL){

        forward = curr -> next;

        curr -> next = prev;

        prev = curr;

        curr = forward;

    }

    return prev;

}

 

bool isPalindrome(LinkedListNode<int> *head) {

    // Write your code here.

 

    // Find the middle of Linked List

    LinkedListNode<int> *slow = head;

    LinkedListNode<int> *fast = head;

 

    while(slow != NULL && fast != NULL){

        slow = slow -> next;

        fast = fast -> next;

        if(fast != NULL){

            fast = fast -> next;

        }

    }

 

    // Reverse the LinkedList from middle

    LinkedListNode<int> *temp1 = reverse(slow);

    LinkedListNode<int> *temp2 = head;

 

    // Compare the Linkedlist

    while(temp1 != NULL && temp2 != NULL){

        if(temp1 -> data != temp2 -> data){

            return false;

        }

        temp1 = temp1 -> next;

        temp2 = temp2 -> next;

    }

    return true;

 

}

beginners

programming

154 views
0 replies
0 upvotes
Full screen
Console