
Leetcode: Palindrome Linked List (Kotlin)
Leetcode: Palindrome Linked List (Kotlin)
This is an easy Linked List problem on Leetcode. This problem is pretty cool because we can use the last two problems I wrote about to solve this one. I will link the articles later in the article. Palindrome Linked List - LeetCode
Problem Statement
Examples
Constraints
Brainstorm
First, we should define what a palindrome is to better understand the problem. The Oxford dictionary defines it as “a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.”
We can use the two problems we did previously to solve this one. We want to find the middle of the linked list, reverse it, then compare it with the original list up to the middle.
Note that the reversed list is the second half of the list. We will check each value of the reversed list and the first half of the list. If any of the values are not equal, then it is not a palindrome. If all values are the same, we will return true at the end.
Solution
/**
* 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 middle = findMiddle(head)
var reversedMiddle = reverseList(middle?.next)
var tmp = head
while(tmp != null && reversedMiddle != null){
if(tmp?.`val` != reversedMiddle?.`val`)return false
tmp = tmp?.next
reversedMiddle = reversedMiddle?.next
}
return true
}
private fun reverseList(head:ListNode?): ListNode?{
var tmp = head
var prev : ListNode? = null
while(tmp != null){
val next = tmp?.next
tmp?.next = prev
prev = tmp
tmp = next
}
return prev
}
private fun findMiddle(head:ListNode?): ListNode?{
var slow = head
var fast = head?.next
while(fast != null && fast?.next != null){
slow = slow?.next
fast = fast?.next?.next
}
return slow
}
}