# Palindrome Linked List Leetcode Solution

Difficulty Level Easy
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Linked-List Two PointersViews 3063

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:

```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.

### 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():
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;
}
};

{
return true;
return false;
return false;
front = front->next;
return true;
}

{
}

int main()
{

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

#### Java Program

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

{
static listNode front;
public static void main(String args[])
{

}

{
return true;
return false;
return false;
front = front.next;
return true;
}

{
}
}```
`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.

#### 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. ### Algorithm

• return true
• 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
• return prev
4. Now, intialise two pointers ptr1 and ptr2 to iterate through both halves:
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

### 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;
}
};

{
while(fast->next != NULL && fast->next->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

{
listNode *prev = NULL;
{
}
return prev;
}

{
return true;
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()
{

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

#### Java Program

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

{
public static void main(String args[])
{

}

{
while(fast.next != null && fast.next.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

{
listNode prev = null;
{
}
return prev;
}

{
return true;
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.

#### Space Complexity

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

Translate »