Reverse Nodes in k-Group

💬 문제

[문제 링크]

연결 리스트의 첫 번째 노드 head
노드들을 k개씩 묶어 역순으로 배치
남은 노드들은 원래 순서를 유지

✍️ 나의 풀이

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let res = new ListNode(0, null);
    let curr = res;
    let stack = [];

    while (head) {
        for (let i = 0; i < k && head; i++) {
            stack.push(head);
            head = head.next;
        }
        if (stack.length === k) {
            while (stack.length > 0) {
                curr.next = stack.pop();
                curr = curr.next;
            }
        } else {
            while (stack.length > 0) {
                curr.next = stack.shift();
                curr = curr.next;
            }
        }
    }
    curr.next = null;

    return res.next;
};

스택을 활용하여 k개씩 노드에 저장한 다음
하나씩 pop하여 새로운 head(res)에 next로 연결
스택에 k개 보다 적게 저장되었다면
정방향으로 연결하기 위해 shift 사용
사이클 제거를 위해 마지막 노드는 next를 null로 설정

📌 결과

Accepted
Runtime 72ms (Beats 50.91%)
Memory 53.07MB (Beats 44.56%)

📚 러닝 포인트

진짜 hard 문제 다웠다. 거의 세 시간을 부었는데도 해결하지 못했다... 결국 솔루션을 보고 스택 활용 알고리즘을 적용해봤다. 정말 간편하고 획기적인 방법이지만, 문제에서 도전 목표로 설정한 공간 복잡도 O(1)은 달성하지 못한다. 한 번만 순회하면서 역순으로 바꾸려고도 해봤고, 부분 리스트를 생성해서 이어 붙이는 방법도 도전해보고 했는데 계속 이전 묶음의 마지막 노드와 다음 묶음의 첫 번째 노드를 연결 시키는 방법에서 막혔다. 꼭 해내고 싶었는데 일단 여기서 마무리 짓는다. 다음에 시간이 나면 다시 도전해서 너를 격파시켜주겠다!