Description
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Examples:
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: falseSolution in Python
Approach:
- Find the middle of the linked list: We’ll use the slow and fast pointer technique to find the middle of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end, the slow pointer will be at the middle.
- Reverse the second half: After finding the middle, we will reverse the second half of the list.
- Compare the first half and the reversed second half: Finally, we compare the values of the first half and the reversed second half. If they are the same, then the list is a palindrome.
- Restore the list (Optional): If required, we can restore the second half back to its original order by reversing it again.
Python
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# Step 1: Find the middle of the linked list using slow and fast pointers
slow = head
fast = head
# Move slow by 1 step and fast by 2 steps to find the middle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse the second half of the list from the middle
prev = None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
# Step 3: Compare the first half with the reversed second half
left = head # Start from the beginning of the list
right = prev # Start from the beginning of the reversed second half
while right: # Compare until the end of the reversed part
if left.val != right.val:
return False
left = left.next
right = right.next
return TrueDetailed Explanation:
- Finding the middle:
- We use two pointers:
slowandfast. - The
slowpointer moves one step at a time, and thefastpointer moves two steps at a time. When thefastpointer reaches the end of the list, theslowpointer will be at the middle of the list.
- We use two pointers:
- Reversing the second half:
- After finding the middle, we reverse the second half of the list. This is done by iterating over the nodes starting from the middle, and adjusting the
nextpointers so that the list is reversed. previs used to keep track of the reversed portion, andslowmoves through the second half of the list, reversing the links as it progresses.
- After finding the middle, we reverse the second half of the list. This is done by iterating over the nodes starting from the middle, and adjusting the
- Comparing the first and second halves:
- After reversing the second half, we compare the values of the nodes in the first half (from the head) with the values in the reversed second half.
- If any pair of corresponding nodes have different values, we return
False. - If all corresponding nodes have the same values, we return
True.
- Optional Step (Restoring the list):
- If required, we can reverse the second half of the list back to its original form. This step is not necessary for solving the problem but can be included if preserving the original structure of the list is needed.
Time Complexity:
- O(n), where
nis the number of nodes in the list. We traverse the list to find the middle, reverse the second half, and then compare both halves.
Space Complexity:
- O(1), since we only use a few extra pointers and do not require additional memory proportional to the size of the list.
This approach ensures that we solve the problem in linear time with constant space (excluding the input and output).
Solution in Javascript
JavaScript
var isPalindrome = function(head) {
// Step 1: Find the middle of the linked list using slow and fast pointers
let slow = head;
let fast = head;
// Move slow by 1 step and fast by 2 steps to find the middle of the list
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the list from the middle
let prev = null;
while (slow !== null) {
let nextNode = slow.next;
slow.next = prev;
prev = slow;
slow = nextNode;
}
// Step 3: Compare the first half with the reversed second half
let left = head; // Starting from the beginning of the list
let right = prev; // Starting from the beginning of the reversed second half
// Compare node values in both halves
while (right !== null) {
if (left.val !== right.val) {
return false; // If values don't match, it's not a palindrome
}
left = left.next;
right = right.next;
}
// If all values matched, the linked list is a palindrome
return true;
};Solution in Java
Java
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true; // A list with 0 or 1 node is trivially a palindrome
}
// Step 1: Find the middle of the linked list using slow and fast pointers
ListNode slow = head;
ListNode fast = head;
// Move slow by 1 step and fast by 2 steps to find the middle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the list starting from the middle
ListNode secondHalfHead = reverseList(slow);
// Step 3: Compare the first half and the reversed second half
ListNode firstHalfPointer = head;
ListNode secondHalfPointer = secondHalfHead;
while (secondHalfPointer != null) {
if (firstHalfPointer.val != secondHalfPointer.val) {
return false; // Mismatch, so it's not a palindrome
}
firstHalfPointer = firstHalfPointer.next;
secondHalfPointer = secondHalfPointer.next;
}
// Step 4 (Optional): Restore the original structure of the second half (if needed)
// reverseList(secondHalfHead); // Uncomment this if you need to restore the list
return true; // All values matched, it's a palindrome
}
// Helper method to reverse a linked list from a given node
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextNode = current.next;
current.next = prev; // Reverse the pointer
prev = current; // Move prev to the current node
current = nextNode; // Move to the next node
}
return prev; // New head of the reversed list
}
}Solution in C#
C#
public class Solution {
public bool IsPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true; // A list with 0 or 1 node is always a palindrome
}
// Step 1: Find the middle of the linked list using slow and fast pointers
ListNode slow = head;
ListNode fast = head;
// Move slow by 1 step and fast by 2 steps to find the middle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the list starting from the middle
ListNode secondHalfHead = ReverseList(slow);
// Step 3: Compare the first half with the reversed second half
ListNode firstHalfPointer = head;
ListNode secondHalfPointer = secondHalfHead;
while (secondHalfPointer != null) {
if (firstHalfPointer.val != secondHalfPointer.val) {
return false; // If mismatch, the list is not a palindrome
}
firstHalfPointer = firstHalfPointer.next;
secondHalfPointer = secondHalfPointer.next;
}
// Step 4 (Optional): Restore the second half (if needed)
// ReverseList(secondHalfHead); // Uncomment this if the list needs to be restored
return true; // The list is a palindrome
}
// Helper function to reverse a linked list from a given node
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextNode = current.next;
current.next = prev; // Reverse the current node's pointer
prev = current; // Move prev to the current node
current = nextNode; // Move to the next node
}
return prev; // Return the new head of the reversed list
}
}