# 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:

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.

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.

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.

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.

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:

if not head or not head.next:

return True

```
# Find length of the linked list
length = 0
node = head
while node:
length += 1
node = node.next
# Find middle node
middle = length // 2
slow = head
fast = head
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
node1 = head
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; secondHead.next = prev; prev = secondHead; secondHead = temp; } // compare the first and second half while (prev != null) { if (head.val != prev.val) { return false; } head = head.next; 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. first_half_end = self.end_of_first_half(head) second_half_start = self.reverse_list(first_half_end.next) # Check whether or not there's a palindrome. result = True first_position = head 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 def end_of_first_half(self, head): slow = head fast = head while fast.next is not None and fast.next.next is not None: slow = slow.next fast = fast.next.next return slow def reverse_list(self, head): previous = None current = head 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 if (!head || !head.next) return true; // 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; } head = head->next; 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 ListNode firstHalfHead = head; while (firstHalfHead != null && secondHalfHead != null) { if (firstHalfHead.val != secondHalfHead.val) { return false; } firstHalfHead = firstHalfHead.next; secondHalfHead = secondHalfHead.next; } 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; } }