Rotate List

Rotate List

Rotate List - LeetCode

- 문제 내용 : 주어진 Linked 전체를 우측으로 k번 옮긴 새로운 Linked List를 return 해라 

- 접근 방법

몇 번째의 노드가 새로운 head가 될 것이냐를 찾는 문제이다.

위와 같이 문제가 나왔다고 하면 k번째에 따라 다음과 같은 변화가 일어난다.

여기서 알수 있는 Rule은 k번째가 0번, 2번, 4번이라고 하면 변화가 없다는 것이다.

즉, k가 node의 길이와 같다면 변화가 불 필요 함으로 다음과 같이 인지 할 수있다.

length == k % length => 차이가 없음

이걸 수식으로 하면 다음과 같다.

nextHeadPosition = length - (k%length)

그런데 우리가 해야할 일이 하나 더 있다.

바로 null 노드의 존재이다.

새롭게 만들어질 head 노드의 바로 앞 노드는 null이 되어야 하고, 새롭게 만들어진 노드는 다음 노드를 순환 해야한다.

상기에서 보면 2번 노드 다음은 null이였는데 1을 다신 Pointing하고 있는 것을 확인 할 수있다.

이 두가지 Condition을 만족하기 위해서 새롭게 만들어질 head의 position 대신 바로 직전의 tail Position을 찾아야 한다.

nextTailPosition = length - (k%length) -1

새롭게 만들어질 Head 대신 Tail을 찾음으로써 Tail 이후는 null을 만들고, Tail.next를 새로운 Head로 만들면 된다.

그럼 2다음에 1을 연결하는건 언제 하는가?

이건 length를 count할때 미리 node를 순환하게 만들어 주면 된다.

이건 getCount 코드를 보면 알 수 있다.

    let getCount = (node,count=1) => {
        if(node.next){
            return getCount(node.next, count+1);  
        } else {
            node.next = head;
            return count;
        }  
    }

노드의 전체 길이를 돌려주기 전에 node.next = head를 통해 순환 linked lisk를 만들었다.

전체 코드는 다음과 같다.

var rotateRight = function(head, k) {
    if(head == null) return head;
    if(head.next == null) return head;
    
    let getCount = (node,count=1) => {
        if(node.next){
            return getCount(node.next, count+1);  
        } else {
            node.next = head;
            return count;
        }  
    }
    
    let length = getCount(head);
    
    let startHeadPosition = length - (k%length) - 1;
    let preHead = null;
    
    for(let i = 0; i < startHeadPosition; i++){
        head = head.next;        
    }
    
    let resultHead = head.next;
    head.next = null;
    
    return resultHead;
};

시간 복잡도는

O(노드길이)

이다.