(LeetCode) 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

1
2
Input: head = [1,2,2,1]
Output: true

Example 2

1
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* 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에 반대로 연결해준다.
  • frontrear를 동시에 순회하면서 값을 비교해서 하나라도 다르면 팰린드롬이 아니고, 그 외엔 팰린드롬이 성립한다.