[LeetCode] 234. Palindrome Linked List - kotlin

/**
 * 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 {
        if (head?.next == null) return true
        var prev: ListNode? = null
        var slow = head
        var fast = head
        while (fast != null && fast.next != null) {
            fast = fast?.next?.next
            val slowNext = slow?.next
            slow?.next = prev
            prev = slow
            slow = slowNext
        }

        var firstHalf = prev
        var secondHalf = if (fast == null) slow else slow?.next

        while (firstHalf != null) {
            if (firstHalf?.`val` != secondHalf?.`val`) return false
            firstHalf = firstHalf?.next
            secondHalf = secondHalf?.next
        }
        return true
    }
}

 

1. **빠른 포인터(fast)와 느린 포인터(slow)**를 이용해 리스트의 중간 지점을 찾는다.

2. 리스트를 순회하면서 첫 번째 절반(head부터 slow 전까지)을 뒤집어(reverse) 놓는다.

• 즉, 중간에 다다르기 전까지 slow 포인터가 가리키는 노드를 계속 거꾸로 연결해 나감.

3. 중간 이후(두 번째 절반)와 뒤집힌 첫 번째 절반을 비교해 같은지 확인한다.