[LeetCode] 2130. Maximum Twin Sum of a Linked List(Kotlin)
풀이 1
- Linked List 자료구조 List로 변환 후, 인덱스로 접근하여 PairSum 계산
import kotlin.math.*
class Solution {
fun pairSum(head: ListNode?): Int {
val headList = convertHeadToList(head)
val n = headList.size
var maxPairSum = 0
for(left in 0 until n/2){
maxPairSum = max(maxPairSum, headList[left] + headList[n-left-1])
}
return maxPairSum
}
private fun convertHeadToList(head: ListNode?):List<Int>{
val headList = mutableListOf<Int>()
var curNode = head
while(curNode != null){
headList.add(curNode.`val`)
curNode = curNode.next
}
return headList.toList()
}
}
풀이2
- Linked List 자료구조 양방향 Linked List로 변환 후, 포인터로 접근하여 PairSum 계산
- 코드는 풀이 1에 비해 복잡해졌지만, 효율은 크게 다르지 않다.
data class BiDirNode(
val value : Int,
var prev: BiDirNode? = null,
var next: BiDirNode? = null
)
class Solution {
fun pairSum(head: ListNode?): Int {
if(head == null) return 0
val biDirNodePair = convertHeadToBiDirList(head!!)
var left = biDirNodePair.first
var right = biDirNodePair.second
var maxPairSum = left.value + right.value
while(left.next != right){
left = left.next!!
right = right.prev!!
maxPairSum = max(maxPairSum, left.value + right.value)
}
return maxPairSum
}
fun convertHeadToBiDirList(head:ListNode): Pair<BiDirNode, BiDirNode>{
var biDirHead: BiDirNode? = null
var curNode: ListNode = head
var fastNode:ListNode? = head.next
var prevBiDirNode: BiDirNode? = null
while(true){
val curBiDirNode = BiDirNode(
value = curNode.`val`,
prev = prevBiDirNode
)
prevBiDirNode?.next = curBiDirNode
if(biDirHead == null) biDirHead = curBiDirNode
prevBiDirNode = curBiDirNode
if(fastNode == null) break
curNode = fastNode
fastNode = fastNode.next
}
prevBiDirNode!!.next = null
return biDirHead!! to prevBiDirNode!!
}
}