700391. Palindrome Linked List
Here is the detailed Markdown blog post for the Palindrome Linked List problem:
Check if Linked List is Pallindrome
Summary
Given a singly linked list, check if it is a palindrome or not. A palindrome linked list is one where the linked list remains unchanged when read from both ends. For example, 1 -> 2 -> 3 -> 2 -> 1 is a palindrome linked list while 1 -> 2 -> 3 -> 4 -> 5 is not.
Detailed Explanation
To solve this problem, we can use two pointers, one starting at the beginning of the linked list and another at the end. We then move both pointers towards each other until they meet in the middle or cross over. If the data stored at each node matches as we move the pointers towards each other, then the linked list is a palindrome.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
startandend, to the beginning and end of the linked list respectively. - Traverse the linked list using the
startpointer until it meets theendpointer in the middle or crosses over. - At each step, compare the data stored at the current node pointed by
startwith the data stored at the node pointed byend. - If all comparisons match and the two pointers meet in the middle or cross over, then the linked list is a palindrome.
Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1), as we only use a constant amount of space to store the two pointers.
Optimized Solutions
Java
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) return true;
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 prev = null;
ListNode curr = slow.next;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
slow.next = null; // disconnect the second half
// Compare the first and second halves
ListNode start = head;
ListNode end = prev;
while (start != null && end != null) {
if (start.val != end.val) return false;
start = start.next;
end = end.next;
}
return true;
}
}