Slow and Fast Pointers: 234. Palindrome Linked List
Question:
Given the head of a singly linked list, return true if it is a palindrome.
Example 1:
Input: head = [1,2,2,1] Output: true
Example 2:
Input: head = [1,2] Output: false
Constraints:
The number of nodes in the list is in the range [1, 105]. 0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
Solution:
- Break the original linkedlist at the middle. (Make sure the node that becomes the head of the later half is correctly identified).
- Reverse the later half of the original LinkedList.
- Iterate through both the halves of the linkedlist;
- If any element is unequal whilst being at the same position (read index) of both LinkedLists, then return false. Original List is not palindrome in this case.
- If we don't find any such element, then return true. List is indeed Palindromic.
Code:
class Solution {
public boolean isPalindrome(ListNode head) {
if(head.next == null) return true;
ListNode mid = findMiddle(head), secondHead = mid.next;
ListNode newHead = reverse(secondHead);
while(newHead != null){
if(head.val == newHead.val) {
head = head.next;
newHead = newHead.next;
}
else return false;
}
return true;
}
static ListNode reverse(ListNode head){
ListNode prev = null, curr = head, next = curr.next;
while(curr != null){
curr.next = prev;
prev = curr;
curr = next;
if(curr == null) break;
else next = curr.next;
}
return prev;
}
static ListNode findMiddle(ListNode head){
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
Complexity:
- Time: O(N)
- Space: O(1)