Similar Problems
Similar Problems not available
Palindrome Linked List  Leetcode Solution
LeetCode: Palindrome Linked List Leetcode Solution
Difficulty: Easy
Topics: stack linkedlist twopointers
The Palindrome Linked List problem on LeetCode asks us to determine if a given singlylinked 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.
Palindrome Linked List Solution Code
1