[LeetCode] 25. Reverse Nodes in k-Group

https://leetcode.com/

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k  is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

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

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

 

Example 2:

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

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

 

Constraints:

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

 

Code :

var reverseKGroup = function(head, k) {
    // 노드 값을 저장할 배열 list 선언
    let list = new Array();
    
    // head가 null이 아닐 때까지 반복하여 list에 노드 값을 추가
    while (head !== null) {
        list.push(head.val);
        head = head.next;
    }

    // list의 길이가 0이면 null 반환
    if (list.length === 0) return null;

    // k씩 노드를 뒤집기 위한 반복문
    for (let i = 0; i < list.length; i += k) {
        // temp 배열에 i부터 i+k까지의 노드 값 할당
        let temp = list.slice(i, i+k);
        // temp의 길이가 k보다 작으면 continue하여 뒤집지 않고 다음 노드 그룹으로 이동
        if (temp.length < k) continue;
        // k개의 노드를 뒤집기 위한 반복문
        for (let j = 0; j < k; j++) {
            // list에서 i+j번째 노드를 temp의 (k-j-1)번째 노드 값으로 덮어씀
            list[i+j] = temp[k-j-1];
        }
    }

    // 결과를 담을 result 노드 초기화
    let result = new ListNode(list.pop());
    // list의 길이가 0보다 클 때까지 반복하여 연결 리스트 생성
    while (list.length > 0) {
        result = new ListNode(list.pop(), result);
    }

    // 결과 반환
    return result;
};

 

Solutions Code :

var reverseKGroup = function(head, k) {
    // 가장 처음의 더미 노드 생성
    var dummy = new ListNode(0);
    dummy.next = head;
    var prevGroupTail = dummy;

    // head가 존재하는 동안 반복
    while (head) {
        // 현재 그룹의 시작점 할당
        var groupStart = head;
        // 현재 그룹의 끝점 계산
        var groupEnd = getGroupEnd(head, k);

        // 그룹의 끝이 존재하지 않을 경우 반복 종료
        if (!groupEnd)
            break;

        // 이전 그룹의 꼬리를 현재 그룹의 뒤집힌 리스트의 헤드로 설정
        prevGroupTail.next = reverseList(groupStart, groupEnd.next);
        prevGroupTail = groupStart;
        head = prevGroupTail.next;
    }
    // 더미 노드의 다음 노드를 새로운 헤드 노드로 설정
    var newHead = dummy.next;
    return newHead;
}

// 그룹의 끝점을 찾는 함수
var getGroupEnd = function(head, k) {
    while (head && k > 1) {
        head = head.next;
        k--;
    }
    return head;
}

// 노드를 뒤집는 함수
var reverseList = function(head, stop) {
    var prev = stop;
    while (head !== stop) {
        var next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode