# Solution For Palindrome Linked List

The Palindrome Linked List problem on LeetCode asks us to determine if a given singly-linked list is a palindrome. A palindrome is defined as a sequence of characters (or in this case, nodes) which reads the same backward as forward.

To solve this problem, we can use several approaches. One of the easiest methods is to reverse the second half of the linked list and then compare the first half with the reversed second half. Another method is to use a stack to store the first half of the linked list in reverse order and then compare it with the second half.

Here is a detailed solution using the first approach:

1. First, we need to determine the length of the linked list. We can do this by traversing the linked list and counting the number of nodes.

2. Next, we need to find the middle node of the linked list. We can use the fast and slow pointer method to find the middle node. The fast pointer moves two nodes at a time, while the slow pointer moves one node at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

3. We can then reverse the second half of the linked list. To do this, we need to split the linked list into two separate lists at the middle node. We can do this by setting the next pointer of the node before the middle node to null.

4. We can then reverse the second half of the linked list using the iterative method. We need to have three pointers: prev, current, and next. We set prev to null, current to the head of the second half, and next to the next node of current. We then iterate through the second half, setting the next pointer of the current node to prev, and moving each pointer one node at a time.

5. We can then compare the first half with the reversed second half. We can use two pointers, one starting from the head of the first half, and the other starting from the head of the reversed second half. We iterate through both halves, comparing each node one at a time. If at any point we find that two nodes are not equal, we can return false, since the linked list is not a palindrome. If we reach the end of both halves and all nodes are equal, we can return true, since the linked list is a palindrome.

Here is the Python code for the solution:

“`
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
return True

``````    # Find length of the linked list
length = 0
while node:
length += 1
node = node.next

# Find middle node
middle = length // 2
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next

# Reverse second half of the linked list
prev = None
current = slow.next
while current:
next = current.next
current.next = prev
prev = current
current = next
slow.next = prev

# Compare first half with reversed second half
node2 = prev
while node1 and node2:
if node1.val != node2.val:
return False
node1 = node1.next
node2 = node2.next

return True
``````

“`

The time complexity of this solution is O(n), where n is the length of the linked list, since we only need to traverse the linked list once. The space complexity is O(1), since we only need to use a constant amount of extra space to store pointers.

## Step by Step Implementation For Palindrome Linked List

```/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
// base case
if (head == null || head.next == null) {
return true;
}

// find middle of the linked list
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// reverse the second half of the linked list
ListNode secondHead = slow.next;
slow.next = null;
ListNode prev = null;
while (secondHead != null) {
ListNode temp = secondHead.next;
}

// compare the first and second half
while (prev != null) {
if (head.val != prev.val) {
return false;
}
prev = prev.next;
}

return true;
}
}```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# Base cases:
# - empty list: considered a palindrome
if head is None:
return True
# - single element list: considered a palindrome
if head.next is None:
return True

# Find the end of the first half and reverse the second half.
second_half_start = self.reverse_list(first_half_end.next)

# Check whether or not there's a palindrome.
result = True
second_position = second_half_start
while result and second_position is not None:
if first_position.val != second_position.val:
result = False
first_position = first_position.next
second_position = second_position.next

# Restore the list and return the result.
first_half_end.next = self.reverse_list(second_half_start)
return result

while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
return slow

previous = None
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous```
```/**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
// edge case: if head is null or only has one node

// find the middle of the linked list
let slow = head;
let fast = head.next;

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

// reverse the second half of the linked list
let prev = null;
let curr = slow.next;

while (curr) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}

// compare the first and second halves of the linked list
slow.next = prev;
let first = head;
let second = slow.next;

while (second) {
if (first.val !== second.val) return false;
first = first.next;
second = second.next;
}

return true;
};```
```/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
// Base case
if (head == nullptr || head->next == nullptr) {
return true;
}

// Find the middle of the linked list
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}

// Reverse the second half of the linked list
ListNode* prev = nullptr;
ListNode* curr = slow;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}

// Compare the first and second half of the linked list
while (prev != nullptr) {
if (head->val != prev->val) {
return false;
}
prev = prev->next;
}

return true;
}
};```
```/**
* Definition for singly-linked list.
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public bool IsPalindrome(ListNode head) {
// base case
if (head == null || head.next == null) {
return true;
}

// find middle node
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// reverse second half
ListNode secondHalfHead = ReverseList(slow.next);

// compare first and second half
while (firstHalfHead != null && secondHalfHead != null) {
return false;
}
}

return true;
}

private ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]