Reverse Nodes in k-Group

Reverse Nodes in k-Group

문제 내용

주어진 Linked List를 주어진 상수 값으로 Reverse Node를 시키면서 Linked List를 유지 시켜라.

예를 들자면

[1,2,3,4,5] 가 주어졌을 때

2라고 하면 2개씩 Linked List를 Reverse 처리한다.

[2,1,4,3,5]

3이면 3개씩

[3,2,1,4,5]

 

접근 방법

우선 문제를 2가지로 나누어서 생각할 필요가 있다.

• 주어진 Linked List 범위를 Reverse 시킨다.
• Reverse된 Linked List를 Group간에 연결을 시켜야 한다.

우선 Linked List를 Reverse 시키는 방법 부터 고민을 해야한다.

위 그림을 예로 들어보자

[1,2,3,4,5] 라고하는 Linked List가 주어지고, 4개의 Node를 Reverse 시킨다고 하면

1번 Node는 가장 처음 head Node이자 최종적으로 Tail Node가 되게 된다.

이점을 이용해서 다음과 같이 코드를 짜면 된다.

1. 첫번째 노드는 head이자 tail이다
2. 다음번에 오는 head 즉 postHead는 tail의 next이다.
3. postHead의 next node는 tail의 다음 Node가 되어야 한다.

이 순서를 지켜서 Reverse code를 짜면 다음과 같다.

    let reversFn = function (rHead,count) {
        let head = rHead;
        let tail = rHead;

        while (1 < count--) {
            let postHead = tail.next;
            tail.next = postHead.next;
            postHead.next = head;
            head = postHead;
        }

        return [head,tail];

    };

 

그럼 reverse된 node의 Group을 엮어 주는 것은 쉽다.

    let resultHead;
    let tTail = head;
    let preTail = null;

    while (0 <= count - k) {

        let [rstHead, rstTail] = reversFn(tTail, k);

        if (resultHead == null) {
            resultHead = rstHead;
        } else {
            preTail.next = rstHead;
        }
        preTail = rstTail;
        tTail = rstTail.next;

        count -= k;
    }

• while (0 <= count - k) {

linked리스트의 남은 노드수가 입력받은 count 수 보다 큰 경우에만 처리한다.

• let [rstHead, rstTail] = reversFn(tTail, k);

특정 Node 여기서는 tTail의 위치 부터 k 개 만큼을 reverse하고 첫번째 Node와 마지막 Node를 갖어 온다.

예를 들자면 상기 그림에서 k가 2이고 tTail이 3이라고 한다면 결과 값은

head인 4와 tail 3이 오게 될 것이다.

        if (resultHead == null) {
            resultHead = rstHead;
        } else {
            preTail.next = rstHead;
        }
        preTail = rstTail;
        tTail = rstTail.next;

이 코드를 더 설명하자면 

resultHead는 preTail이 없는 최초의 경우 임으로 결과 값으로 돌려줄 첫번째 값을 저장한다.

만약에 첫번째 그룹이 정리 되고 두번재 그룹이 오게된다면 반듯이 preTail의 마지막에 현 loop의 head를 붙여 줘야 한다.

그리고 preTail을 다음으로 이동 시켜주면 된다.

전체 코드는 아래와 같다.

var reverseKGroup = function(head, k) {
    let count = 0;
    let node = head;

    while (node){
        count++;
        node = node.next;
    }

    let reversFn = function (rHead,count) {
        let head = rHead;
        let tail = rHead;

        while (1 < count--) {
            let postHead = tail.next;
            tail.next = postHead.next;
            postHead.next = head;
            head = postHead;
        }

        return [head,tail];

    };

    let resultHead;
    let tTail = head;
    let preTail = null;

    while (0 <= count - k) {

        let [rstHead, rstTail] = reversFn(tTail, k);

        if (resultHead == null) {
            resultHead = rstHead;
        } else {
            preTail.next = rstHead;
        }
        preTail = rstTail;
        tTail = rstTail.next;

        count -= k;
    }

    return resultHead;

};

시간 복잡도는 Node 1회 선회를 위한

$$ O(N) $$

이며 공간 복잡도는 별도로 temp space를 만들지 않아서

$$ O(1) $$

이다.