[JavaScript] 61. Rotate List Medium - 연결리스트 노드 옮기기, 쉬운설명, 반복문 사용

61. Rotate List

Given the head of a linked list, rotate the list to the right by k places.

 

Example 1:

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

Example 2: 

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

 

 

계획

문제 해결 전략

 

주어진 k만큼 반복하게 됩니다. 하지만 k가 linkedlist의 길이보다 클경우, example 2와 같이 k를 linkedlist length로 나눈 나머지값 만큼만 반복하면되기때문에 반복문에서 k% linkedlistLength의 값만큼 반복하게 합니다. 

 

linkedList 특성상 index로 요구하는 위치로 이동이 바로 불가능하기때문에 끝에 값을 제거해주고 head로 가져오기위해 가장마지막 값을 node 라는 이름의 포인터로 가르키고,

 

마지막에서 2번째 노드를 prev 라는 이름의 포인터로 가르킨후 prev.next = null이라 지정하여, 우리가 이번 loop에서 앞으로 옮길 node를 현재 linkedList로 부터 제거합니다. 

 

그리고  newhead라는 새로운 listnode를 만들어서 기존에 있던 head를 지우고 new head로 바꿔줘야합니다.

 

이 작업을  k% linkedlistLength 만큼 반복하면 rotate 할수있게 됩니다. 

 

 

해설

 

var rotateRight = function(head, k) {
    if (!head) return head
    
    const length = lengthOfList(head)
    console.log(length)
    
    for (let i = 0; i < (k % length); i++) { //반복문 실행
        let newHead = new ListNode(), node = head, prev = head
        
        while (node.next) { // 링크리스트에 마지막으로 이동
            prev = node
            node = node.next
        }
        
        if (length > 0) { 
            prev.next = null //앞으로 옮길 node를 기존 링크리스트에서 연결을 끊어준후
            newHead.val = node.val //newhead를 새로 만들어서 옮길 node에 val을 insert
            newHead.next = head //그리고 newhead의 다음값을 head로 지정해줌으로써, rotate이됨
            head = newHead // 그리고 가장 앞으로 오게된newhead에게 head를 지정
        }
    }
    
    return head //loop 가 끝나면, head를 리턴
};

const lengthOfList = head => { //length를 찾아주는함수 구현
    let node = head, length = 0
    while (node) { //node가 null이라면 stop
        node = node.next //node를 다음으로 옮겨줌
        length++
    }
    return length
}