level - hard
[문제 내용]
주어진 linked list를 k개씩 뒤집어서 반환
[example 1]
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5][example 2]
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5][example 3]
Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5][example 4]
Input: head = [1], k = 1
Output: [1][해결 방법]
먼저 listNode 형태다.
class ListNode(var `val`: Int) {
var next: ListNode? = null
}노드들을 뒤집은 순서로 저장할 list를 준비한다.
해당 list에 하나씩 꺼내 저장하고
list의 길이가 modulo k가 0일 경우에
끝에서부터 k개를 순서를 바꿔서 list에 저장한다.
예제 1을 예시로 얘기하면
1,2,3,4,5 에서
list에 1,2 를 추가하면 길이가 modulo k가 0인 상태가 된다.
거기서 list를 2, 1로 바꾸고 해당 list 의
맨 처음이 2로 바뀌었음을 head에 따로 저장한다.
다시 3, 4를 추가하고 modulo k가 0이 상태가 다시 되었으니
4, 3으로 순서를 뒤집고 1에게 다음이 4라는걸 명시해준다.
해당 방법을 반복하면 된다.
class Solution {
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
if(k == 1) {
return head
}
val list = mutableListOf<ListNode>()
var parent = head
var now = head
var before: ListNode? = null
while(now != null) {
list.add(now)
now = now.next
if(list.size != 0 &&list.size % k == 0) {
reverse(list, k, before)
if(before == null) {
parent = list[list.size-1]
}
before = list[list.size-k]
}
}
return parent
}
fun reverse(list: MutableList<ListNode>, k: Int, before: ListNode?) {
val index = list.size-1
if(before != null) {
before.next = list[index]
}
val tmp: ListNode? = list[index].next
for(i in 0 until k-1) {
list[index-i].next = list[index-i-1]
}
list[index-k+1].next = tmp
}
}