Leetcode: Palindrome Linked List (Kotlin)
Kotlin

Leetcode: Palindrome Linked List (Kotlin)

December 6, 2024

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
    }


}