LeetCode-in-All
234. Palindrome Linked List
Easy
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
import com_github_leetcode.ListNode
/*
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
class Solution {
fun isPalindrome(head: ListNode?): Boolean {
var fast = head
var slow = head
while (fast?.next != null) {
fast = fast.next?.next
slow = slow?.next
}
var right = reverse(slow)
var left = head
while (right != null && left != null) {
if (right.`val` != left.`val`) {
return false
}
left = left.next
right = right.next
}
return true
}
fun reverse(head: ListNode?): ListNode? {
var prev: ListNode? = null
var current = head
while (current != null) {
val next = current.next
current.next = prev
prev = current
current = next
}
head?.next = null
return prev
}
}