LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 연결리스트의 시작 노드 head, reverse 크기 k
2. output: 주어진 연결리스트를 k개씩 역순 정렬 한 결과 리턴

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Idea

Solution

1. 스택에 연결리스트의 원소 저장하여 역순 정렬

   연결 리스트를 순서대로 스택에 삽입

   • reverse가 되지 않는 부분 (k로 나눈 나머지)

     원래 순서대로 연결

   • reverse가 되는 부분

     스택에서 하나씩 꺼내어(역순) k개씩 연결

   class Solution {
       fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
           // 연결리스트를 스택에 삽입
           val stack = LinkedList<ListNode>()
           var stackCursor = head
           while (stackCursor != null) {
               stack.offer(stackCursor)
               stackCursor = stackCursor.next
           }
           // reverse가 되지 않는 나머지 처리
           var last: ListNode? = null
           for (i in 0 until stack.size % k) {
               val tmp = last
               last = stack.pollLast()
               last.next = tmp
           }
           // k개씩 reverse
           var cnt = 0
           var reversedStart: ListNode? = ListNode(0)
           var reversedCursor = reversedStart
           while (stack.size > 0) {
               reversedCursor?.next = stack.pollLast()
               reversedCursor = reversedCursor?.next
               cnt++
               if (cnt == k) { // 이전의 연결리스트 앞에 연결 시켜주기
                   reversedCursor?.next = last
                   last = reversedStart?.next
                   cnt = 0
                   reversedStart = ListNode(0)
                   reversedCursor = reversedStart
               }
           }
           return last
       }
   }
   

   시간 복잡도: 스택 삽입 n + k개씩 역순 정렬 n = n

   

Point