[leetcode 234] Palindrome Linked List

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

해결 과정

206번 문제와 876번 문제를 합쳐놓은 문제로 보았다.

1. STEP1. 느린 포인터(slow)와 빠른 포인터(fast) 2개를 사용하여, 반을 기준으로 뒷쪽 첫번째 노드를 가리킬 때까지 slow 를 이동시킨다.

• 홀수/짝수를 나누어 생각해야 하는데,
  • 짝수: 빠른 포인터가 null 일때까지 이동, slow는 뒷쪽 첫번쨰 노드를 가리킴.
  • 홀수: 빠른 포인터가 null이 아니며, slow는 가운데 노드를 가리킴.

1. STEP2. 뒷쪽 첫번째 노드를 가리킬 수 있도록, 홀수 케이스에는 slow를 하나 더 이동시켜준다.

2. STEP3. slow 가 가리키는 뒤쪽 뭉치를 resverse 시킨 후,

3. head 가 가리키는 앞쪽 뭉치와 revere한 뒤쪽 뭉치들의 값을 하나씩 비교한다.

코드

fun isPalindrome(head: ListNode?): Boolean {
    if(head == null) return true

    var slow = head
    var fast = head
    while(fast !=null && fast.next != null) {
        slow = slow?.next
        fast = fast?.next?.next
    }

    if(fast != null) {
        slow = slow?.next
    }

    slow = reverse(slow)
    fast = head
        
    while(slow != null) {
        if(slow.`val` != fast?.`val`) {
            return false
        }
        slow = slow.next
        fast = fast.next
    }
        
    return true
}
    
private fun reverse(current: ListNode?): ListNode? {
    var temp: ListNode? = null
    var prev: ListNode? = null
    var current: ListNode? = current
        
    while(current != null) {
        temp = current.next
        current.next = prev
        prev = current
        current = temp
    }
    return prev
}

배운 점

• 문제 풀이 방법이 재사용될 수 있음.
• 홀수/짝수 구분.