(LeetCode) 234. Palindrome Linked List

Palindrome Linked List

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Linked List
• 난이도 : Easy

Problem

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, 10^5].
• 0 <= Node.val <= 9

Solution

Exapnder

/**
 * 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 front = head
        var rear = head

        while (front?.next?.next != null) {
            front = front?.next?.next
            rear = rear?.next
        }

        var cursor = rear?.next

        front = head
        rear = null
        while (cursor != null) {
            val temp = cursor.next
            cursor.next = rear
            rear = cursor
            cursor = temp
        }

        while (front != null && rear != null) {
            if (front.`val` != rear.`val`) {
                return false
            }
            front = front.next
            rear = rear.next
        }
        return true
    }
}

Point of Thinking

• 팰린드롬 검증을 위해 Stack을 쓰고 싶었으나 시간 복잡도 O(n)과 공간 복잡도 O(1)에 도전해보라고 해서 순회로만 처리해보았다
• 주어지는 노드의 끝까지 rear로 순회한 뒤, cursor에 세팅해서 rear에 반대로 연결해준다.
• front와 rear를 동시에 순회하면서 값을 비교해서 하나라도 다르면 팰린드롬이 아니고, 그 외엔 팰린드롬이 성립한다.