Table of contents
1.
Introduction
2.
Approach
2.1.
Dry Run on a sample test
2.2.
Pseudocode
2.3.
Implementation in C++
2.4.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
Can we access a node directly in a linked list?
3.2.
Is it necessary to initialize the last node address as null?
3.3.
Why sometimes do I get a segmentation fault?
3.4.
What is the difference between an array and a linked list?
3.5.
What do you mean by palindrome?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Length of the Most Extended Palindrome List in a Linked List using O(1) Extra Space

Author Urwashi Priya
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Linked List

Introduction

In this blog, we will discuss a linked list problem that has been asked frequently in Interviews.

The problem is to find the Length of the most extended palindrome list in a linked list using O(1) extra space.

I am starting with what is a linked list.

It is an ordered set of elements, each holding data and a link containing the address to the next element.

To know more about the linked list, refer here

Illustration Image

We are now coming to the question.

We are given N elements in a linked list, and we are asked to find the Length of the most extended palindrome list in a linked list using O(1) extra space.

For example, the given list is:

 

Illustration Image

The most extended palindromic list here is 2->4->3->4->2.

Length=5

Also see, Data Structures

Approach

Now we will discuss the approach to find the Length of the most extended palindrome list in a linked list using O(1) extra space.

 

Declare the Node structure and write the function to create and return the node.

Declare and define a function to return common elements in a list.

Declare function to return the length of the longest palindromic sublist.

  • Start looping till the end of the linked list.
  • Reverse each time the elements from head to the current value.
  • If we encounter an odd length palindromic sublist, our result will be 2*count of common elements + 1. This 1 has been added to include the current element as well. 
  • If we encounter an even length palindromic sublist, our result will be 2*count of common elements. We multiplied by 2 because common elements from both lists must be considered.
  • Update previous and current elements for the next iteration.

Return result.

 

Time Complexity = O(n²).

Since in the worst case, two traversals is needed.

Space Complexity = O(1).

Recommended Topic, Floyds Algorithm

Dry Run on a sample test

Say our list is 2->4->3->4->2->15.

previous=NULL, current=head.(head is the starting position i.e: 2)

So the first list formed will be 2. (on reversing 2, it remains the same.)

The second list formed will be 4->3->4->2->15.

Common element = 0.

The next step does not include a current element(4),

Now, the first list formed will be 2. (on reversing this, we get the same.)

The second list formed will be 3->4->2->15.

Common element = 0.

Next step,

Now, the first list formed will be 2->4. (on reversing this, we get 4->2.)

The second list formed will be 3->4->2->15.

Common element = 0.

The next step does not include a current element(3),

Now, the first list formed will be 2->4. (on reversing this, we get 4->2.)

The second list formed will be 4->2->15.

Common element = 2.

∴Result=2*2+1=5

Here 2 is multiplied because we have to take care of both lists.

And, 1 is added because we have excluded the current element.

Next step,

Now, the first list formed will be 2->4->3. (on reversing this, we get 3->4->2.)

The second list formed will be 4->2->15.

Common element = 0.

The next step does not include a current element(4),

Now, the first list formed will be 2->4->3. (on reversing this, we get 3->4->2.)

The second list formed will be 2->15.

Common element = 0.

Next step,

The first list formed will be 2->4->3->4. (on reversing this, we get 4->3->4->2.)

The second list formed will be 2->15.

Common element = 0.

Next step not including the current element(2),

The first list formed will be 2->4->3->4. (on reversing this, we get 4->3->4->2.)

The second list formed will be 15.

Common element = 0.

Next step,

Now, the first list formed will be 2->4->3->4->2. (on reversing this, we get 2->4->3->4->2.)

The second list formed will be 15.

Common element = 0.

And so on.

Maximum common element found=5.

So, return 5.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

And solve some related problems on the linked list.

Some Commonly Asked Problems On Linked List

Pseudocode

Algorithm

___________________________________________________________________

procedure maxPalindrome( Node *head ):

___________________________________________________________________

1.   result=0

      Node *prev = NULL, *curr = head;

2.   Begin loop and continue till curr->next==NULL

3.   Node *next = curr->next;

      curr->next = prev;

4.   result = max(result, 2*countCommon(prev, next)+1);

5.   result = max(result, 2*countCommon(curr, next));

6.   prev = curr;

      curr = next;

7. End loop and return result.

end procedure

___________________________________________________________________

Implementation in C++

// Length of the most extended palindrome list in a linked list using O(1) extra space
#include<bits/stdc++.h>

using namespace std;

//declaring the structure of the linked list
struct Node {
    int data;
    struct Node * next;
};

// function used for keeping track of the common(exact similar) elements
int countCommon(Node * a, Node * b) {
    int count = 0;

    // loop to calculate length of common elements
    for (; a && b; a = a -> next, b = b -> next)

        // incrementing the count for same values
        if (a -> data == b -> data)
            ++count;
        else
            break;

    return count;
}

// Returns length of the longest palindrome sublist 
int maxPalindrome(Node * head) {
    int result = 0;
    Node * prev = NULL, * curr = head;

    // looping till the end of the linked list
    while (curr) {
        // The sublist found is reversed.
        Node * next = curr -> next;
        curr -> next = prev;

        // checking for odd length palindrome by finding longest common list elements beginning from prev and from next 
        result = max(result, 2 * countCommon(prev, next) + 1);

        // checking for even length palindrome by finding longest common list elements beginning from curr and from next
        result = max(result, 2 * countCommon(curr, next));

        // updating prev and curr for next iteration
        prev = curr;
        curr = next;
    }
    return result;
}

//function to create a new list node
Node * newNode(int key) {
    Node * temp = new Node;
    temp -> data = key;
    temp -> next = NULL;
    return temp;
}

int main() {

    Node * head = newNode(2);
    head -> next = newNode(4);
    head -> next -> next = newNode(3);
    head -> next -> next -> next = newNode(4);
    head -> next -> next -> next -> next = newNode(2);
    head -> next -> next -> next -> next -> next = newNode(15);

    cout << maxPalindrome(head) << endl;
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

Input:  2->4->3->4->2->15
Output:  5

 

Complexity Analysis

Time Complexity: O(n²).

Analyzing Time Complexity:

In the worst case, all elements are to be traversed twice.O(n^2)

Space complexity: O(1) since no extra variable is used.

Check out this problem - Reverse Nodes In K Group

You can also read about Palindrome Number in Python here.

Frequently Asked Questions

Can we access a node directly in a linked list?

Unlike an array, this is not possible in a linked list.

Is it necessary to initialize the last node address as null?

Yes, as elements are not stored in a contiguous manner, pointers are used, so sometimes it may take the garbage value.    

Why sometimes do I get a segmentation fault?

This is most likely if we try to access NULL or out of bounds memory.

What is the difference between an array and a linked list?

The array consists of a similar data type, which is not necessary in the case of a linked list. The array is stored in a contiguous memory location, whereas a linked list can be stored randomly.

What do you mean by palindrome?

A sequence of characters reading the same from both forward and backward directions.

Conclusion

This article taught us how to find the Length of the most extended palindrome list in a linked list using O(1) extra space. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most linked list problems.

Now, we recommend you practice problem sets based on the linked list to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding.

Live masterclass