LeetCode 25 - Reverse Nodes in k-Group - Hard (Java)

  리스트 구현을 직접 해봤다면 어렵지 않게 풀 수 있는 문제이다. 다만 O(N)에 풀 수 있는 아이디어는 어쩌면 생각하기 어려울 수도 있을 것 같다. 원본 리스트를 순회하며 reverse 할 항목들을 tmp배열에 넣어둔 뒤, k개 만큼 채워졌다면 역순으로 결과 리스트에 넣는다.(코드에서 idx==k 일 경우)

 

  그리고 마지막에 나누어떨어지지 않는 항목들에 대해서는 리스트의 끝을 만날 경우 tmp에 있는 남은 항목들을 역순이 아니라 원래순서대로 출력해주면 된다.(코드에서 head==null일 경우)

 

  이전에 풀었던 5번 Medium이 더 어려웠던 것 같은데.. 리트코드 난이도 책정 방식이 좀 이상한 것 같다.

 

 

코드 : github

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode answer = null;
    ListNode iter = null;

    private void add(int val) {
        if (iter == null) {
            answer = new ListNode(val);
            iter = answer;
            return;
        }

        iter.next = new ListNode(val);
        iter = iter.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode iter = null;
        if (k <= 1)
            return head;

        int idx = 0;
        int[] tmp = new int[k];
        while (true) {
            tmp[idx++] = head.val;
            head = head.next;

            if (idx == k) {
                idx = 0;
                for (int i = k-1; i >= 0; i--) {
                    add(tmp[i]);
                }
            }

            if (head == null) {
                for (int i = 0; i < idx; i++) {
                    add(tmp[i]);
                }
                break;
            }
        }
        return answer;
    }
}