234. Palindrome Linked List
Palindrome Linked List
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
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?
Revision point 1: A linked list is a data structure that consists of two properties; next which points to the next node in the list, and val which tells you the current node’s value.
Revision point 2: A palindrome is something that is the same when reversed. For example, “dad” is a palindrome, as is “12321”, but “test” is not, and nor is “123”.
What we’re being asked here then, is to get the values from a Linked List, reverse them, and see if they remain the same. For example, in the Linked List 1 -> 2 -> 1, if we pull out the values to make the array [1, 2, 1], and then reverse it, we can see it remains the same and is thus a palindrome.
Approach 1) Array of values
Much like in the above explanation, our approach here will be first to loop through the values of the supplied Linked List, adding them to an array, and then to determine whether or not that array represents a palindrome.
Let`s Code IT!
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
// Store all values from the linked list in an array
let valuesFound = [];
while (head) {
valuesFound.push(head.val);
head = head.next;
}
// Check if the list of values are a palindrome
let left = 0;
let right = valuesFound.length - 1;
while (left <= right) {
if (valuesFound[left] !== valuesFound[right]) {
return false;
}
left++, right--;
}
return true;
};
This approach is fast, but it isn’t great on memory, as we’re creating a new block of data that is proportionate to the original Linked List.
Approach 2) Recursive
In this solution, we first make a recursive call that traverses its way through the supplied Linked List. Then, as each call begins to finish (starting with the final node), we compare it with the original head. In other words, we compare the first node with the last, and then move both inward.
Let`s Code IT!
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
function isPalindromRecursive(recursiveHead) {
// Reached the end of the list
if (recursiveHead == null) {
return true;
}
// Recursively traverse the linked list
const next = isPalindromRecursive(recursiveHead.next);
// Check if the current level of the linked list mirrors its mirror point
const valid = recursiveHead.val === head.val;
// Move the original linked list inward
head = head.next;
return next && valid;
}
return isPalindromRecursive(head);
};Let`s Code IT!
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
// Pass empty or single-item linked lists
if (!head || !head.next) return true;
// Traverse the linked list in order to find the mid-point (slow)
let slow = head,
fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half of the linked list
slow.next = reverseLinkedList(slow.next);
slow = slow.next;
// Compare the original linked list with the reversed second half
while (slow) {
if (head.val !== slow.val) {
// If a mismatch is detected, break out
return false;
}
head = head.next;
slow = slow.next;
}
return true;
};
var reverseLinkedList = function (head) {
let nextNode = null;
let previousNode = null;
while (head) {
nextNode = head.next;
head.next = previousNode;
previousNode = head;
head = nextNode;
}
return previousNode;
};/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
function isPalindrome(head) {
let leftToRightString = "";
let rightToLeftString = "";
let current = head;
while(current) {
leftToRightString += current.val;
rightToLeftString = current.val + rightToLeftString;
current = current.next;
}
return leftToRightString === rightToLeftString ? true : false;
}
Conclusion
That’s all folks! In this post, we solved LeetCode problem #234. Palindrome Linked List
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
Happy coding!
Comments
Post a Comment