-
Notifications
You must be signed in to change notification settings - Fork 0
/
PalindromeLinkedList.kt
185 lines (152 loc) · 4.21 KB
/
PalindromeLinkedList.kt
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/*
* Palindrome Linked List
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
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, 105].
0 <= Node.val <= 9
Follow up: Could you do it in O(n) time and O(1) space?
*/
/**
* 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 reverseLinkedList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var nextNode: ListNode?
var current = head
while (current != null) {
nextNode = current.next
current.next = prev
prev = current
current = nextNode
}
return prev
}
fun isPalindrome(head: ListNode?): Boolean {
if (head == null || head?.next == null)
return true
var fast = head
var slow = head
while (fast != null && fast.next != null) {
fast = fast.next?.next
slow = slow?.next
}
val reverseHead = reverseLinkedList(slow)
var temp1 = head
var temp2 = reverseHead
while (temp2 != null) {
if (temp1?.`val` != temp2.`val`)
return false
temp1 = temp1.next
temp2 = temp2.next
}
return true
}
}
class Solution {
fun isPalindrome(head: ListNode?): Boolean =
sequence { listSequence(head) }
.zip(sequence { reverseListSequence(head) })
.all { (a, b) -> a == b }
private tailrec suspend fun SequenceScope<Int>.listSequence(node: ListNode?) {
if (node == null) return
yield(node.`val`)
listSequence(node.next)
}
private suspend fun SequenceScope<Int>.reverseListSequence(node: ListNode?) {
if (node == null) return
reverseListSequence(node.next)
yield(node.`val`)
}
}
/**
* 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 {
/*
* Complexity: Time O(N) and Space O(1) where N is the length of head;
*/
fun isPalindrome(head: ListNode?): Boolean {
var slow = head
var fast = head
while (fast?.next != null && fast.next?.next != null) {
slow = slow?.next
fast = fast.next?.next
}
fun reverse(node: ListNode?): ListNode? {
var currHead = node
while (node?.next != null) {
val nextNode = node.next
node.next = nextNode?.next
nextNode?.next = currHead
currHead = nextNode
}
return currHead
}
fast = head
var reversed = reverse(slow?.next)
var isPalindrome = true
while (isPalindrome && reversed != null) {
isPalindrome = reversed.`val` == fast?.`val`
reversed = reversed.next
fast = fast?.next
}
reverse(slow?.next)
return isPalindrome
}
}
class Solution {
fun isPalindrome(head: ListNode?): Boolean {
val sb = StringBuilder()
var list = head
while(list != null) {
sb.append(list.`val`)
list = list.next
}
return sb.toString() == sb.reverse().toString()
}
}
class Solution {
/* Complexity:
* Time O(N) and Space O(N) where N is the size of head;
*/
fun isPalindrome(head: ListNode?): Boolean {
return head.toList().isPalindrome()
}
private fun ListNode?.toList(): List<Int> = buildList {
var nodePtr = this@toList
while (nodePtr != null) {
add(nodePtr.`val`)
nodePtr = nodePtr.next
}
}
private fun List<Int>.isPalindrome(): Boolean {
var left = 0
var right = lastIndex
while (left <= right) {
if (this[left] != this[right])
return false
left += 1
right -= 1
}
return true
}
}