[LeetCode # 25] Reverse Nodes in k-Group

리스트가 주어졌을 때, 리스트의 노드 k 개씩을 묶어 순서를 반전시키는 문제

 

리스트 노드들은 다음과 같이 주어진다.

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

리스트를 순차적으로 탐색하면서 매 그룹의 k 번째마다 앞의 노드와 값을 바꾸면 간단히 해결할 수 있다. 하지만 리스트 노드에 이전 노드를 참조하는 포인터 변수는 없기 때문에 이와 같은 방법은 사용이 불가능했다.

마찬가지로 순차적으로 탐색하면서 노드가 가진 값의 순서를 바꿔주는 방법을 생각하다 저장 순서가 서로 다른 스택과 큐를 활용할 수 있겠다는 생각을 했다. 앞에서부터 탐색을 하며 스택에 노드 주소를, 큐에 노드가 가진 값을 저장하고, 스택의 원소 개수가 k 개가 되면 스택과 큐에서 순서대로 노드 주소와 값을 꺼내서 서로를 매칭시켜주면 k 개의 순서를 바꿀 수 있게 된다.

 

위와 같은 풀이로 작성한 코드는 다음과 같다.

 

class Solution {
public:
    stack<ListNode*> nodeStack;
    queue<int> numQueue;
    ListNode* reverseKGroup(ListNode* head, int k) {
        for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next){
            numQueue.push(tmp->val);
            nodeStack.push(tmp);
            if (nodeStack.size() == k){
                while (nodeStack.size()){
                    nodeStack.top()->val = numQueue.front();
                    nodeStack.pop();
                    numQueue.pop();
                }
            }
        }
        return head;
    }
};