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
My Solution
We can solve this problem by iterating through the Linked List and adding all the nodes to an ArrayList. We then use the two pointer technique to check that the list is a palindrome.
Time complexity is O(n), where n is the number of nodes in the Linked List because we do two passes through it. Space complexity is O(n) to maintain the ArrayList.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> arr = new ArrayList<>();
ListNode n = head;
while (n != null) {
arr.add(n.val);
n = n.next;
}
int i = 0;
int j = arr.size()-1;
while (i < j) {
if (arr.get(i) != arr.get(j)) {
return false;
}
i++;
j--;
}
return true;
}
}