[LeetCode] 25. Reverse Nodes in k-Group

문제 출처: https://leetcode.com/problems/reverse-nodes-in-k-group/

Reverse Nodes in k-Group - LeetCode

 

문제

연결 리스트가 주어지면, k개의 연결 리스트의 노드를 동시에 뒤집고, 그 수정된 리스트를 반환하라.

 

k는 양수이고, 연결 리스트의 길이보다 작거나 같다. 만약 노드의 수가 k의 배수가 아닌 경우, 남은 노드는 그대로 있어야 한다.

 

리스트의 노드의 값을 변경할 수는 없으며, 노드 자체의 위치를 변경해야 한다.

 

예제

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

 

Input: head = [1,2,3,4,5], k = 3 
Output: [3,2,1,4,5]

Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]

Input: head = [1], k = 1
Output: [1]

 

풀이

문제 해결을 위한 알고리즘을 만들기 위해서, 우리가 해야 하는 일을 순차적으로 생각해보자.

 

1. 주어진 연결리스트를 k개의 노드를 갖는 연결 리스트로 분해
2. 분해된 각각의 연결 리스트를 역순으로 재배열
   • k개의 노드를 갖지 못하는 해당 연결 리스트는 그대로 유지
3. 2단계에서 만들어진 모든 연결 리스트를 하나로 연결

 

먼저, k개의 노드를 갖는 연결 리스트로 분해를 해보자. 연결 리스트를 k개씩 끊어가면서 읽고 마지막 노드의 next에 null 값을 설정하는 것으로 주어진 연결 리스트를 분해할 수 있다.

var reverseKGroup = function(head, k) {
    // 크기가 k인 연결 리스트로 분해
    const splitList = [];
    
    let cur = head;
    let h = cur;
    
    while (cur != null) {
    	let tail = cur;
        
    	for (let i = 0; i < k; i++) {
            if (cur == null) { break; }
            cur = cur.next;
            if (i < k-1) { tail = cur; }
        }
        
        if (tail) { tail.next = null; }
        splitList.push(h);
        h = cur;
    }
}

분해된 연결 리스트를 뒤집을 때, 다음 단계인 하나로 합치는 과정에 대해 염두해야 한다.

 

하나로 합칠 때 필요한 정보를 생각해보자. 연결 리스트 A와 B가 있다고 한다면, 두 리스트를 합치기 위해서는 A의 마지막 노드(tail)와 B의 첫 노드(head)의 정보가 필요하다. 이 두 노드의 정보는 연결 리스트를 뒤집는 현재 단계에서 쉽게 파악이 가능하므로, 이 정보를 반환하도록 해야 한다.

var reverseKGroup = function(head, k) {
    // 크기가 k인 연결 리스트들로 분해
    ...
    
    // 분해된 리스트 중, 마지막 리스트의 길이 체크
    let lastListSize = 0;
    let lastListCur = splitList[splitList.length - 1];
    while (lastListCur != null) {
    	lastListCur = lastListCur.next;
        lastListSize += 1;
    }
    
    // 분해된 연결 리스트를 역순으로 정렬
    let heads = [],
    	tails = [];
    for (let i = 0; i < splitList.length; i++) {
    	if (i == splitList.length-1 && lastListSize < k) { 
            heads.push(splitList[i]);
            break; 
        }
    	[heads[i], tails[i]] = reversedList(splitList[i]);
    }
}

var reverseList = function(head) {
    const reversedList = null;
    const tail = head;
    let cur = head;
    while (cur != null) {
    	const next = cur.next;
        cur.next = reversedList;
        reversedList = cur;
        cur = next;
    }
    return [reversedList, tail];
}

여러 리스트를 하나로 합치는 과정만이 남아 있다. 이전 단계에서 필요한 정보를 모두 구했기 때문에 손쉽게 하나로 합치는 게 가능하다.

var reverseKGroup = function(head, k) {
    // 크기가 k인 연결 리스트들로 분해
    ...
    
    // 분해된 리스트 중, 마지막 리스트의 길이 체크
    ...
    
    // 분해된 연결 리스트를 역순으로 정렬
    ...
    
    // 하나의 연결 리스트로 병합 및 반환
    let ans = heads[0];
    for (let i = 1; i < heads.length; i++) {
        tails[i-1].next = heads[i];
    }
    return ans;
}

var reverseList = function(head) {
    ...
}

지금까지 문제 해결을 위해 수행해야하는 각 과정을 하나하나씩 나누어 코드로 작성했는데, 이를 합쳐 하나의 반복문 안에서 해결 가능하게 코드를 구성할 수 있다.

var reverseKGroup = function(head, k) {
    let N = 0;
    let cur = head;
    while (cur != null) { N += 1; cur = cur.next; }
    
    let ans = null;
    
    cur = head;
    let ans_tail = cur;
    let numOfGroup = Math.floor(N / k);
    while(numOfGroup > 0) {
        let tmp_list = null;
        let tmp_tail = cur;
        for (let i = 0; i < k; i++) {
            const next = cur.next;
            
            cur.next = tmp_list;
            tmp_list = cur;
            cur = next;
        }
        
        if (numOfGroup == Math.floor(N / k)) {
            ans = tmp_list;
        } else {
            ans_tail.next = tmp_list;
            ans_tail = tmp_tail;
        }
        
        numOfGroup -= 1;
    }
    if (cur != null) { ans_tail.next = cur; }
    
    return ans;
};

기존 코드와 이 코드의 실행 시간은 거의 차이가 없다. 시간 복잡도를 생각해보아도 두 코드는 O(N)으로 같기 때문에 두 방식 중 어떤 것을 택해도 문제가 되지 않는다.

 

 

Github: 25.js

opwe37/Algorithm-Study