Rotate List

💬 문제

[문제 링크]

연결 리스트의 첫 번째 노드 head
오른쪽 방향으로 k번 순환 이동 시킨 결과의
첫 번째 노드 반환

✍️ 나의 풀이

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (head === null)
        return null;
    
    let curr = head;
    let len = 1;

    while (curr.next) {
        len++;
        curr = curr.next;
    }

    curr.next = head;
    let idx = k % len + 1;
    curr = head;
    
    while (len > idx) {
        len--;
        curr = curr.next;
    }

    let temp = curr.next;
    curr.next = null;
    
    return temp;
};

가장 먼저 리스트의 노드 개수를 세기 위해 len을 증가하며 순회
마지막 노드에 도착했을 때 next에 head를 할당하여 cycle을 만들어줌
주어진 k가 len보다 큰 경우 나눴을 때 나머지 만큼만 이동하면 같은 결과이므로
뒤에서 나머지만큼 떨어져 있는 노드가 head가 되면 됨
즉, 뒤에서 나머지 + 1 (idx)번째 노드의 next를 null로 바꿔서 cycle을 끊어줌
기존의 next는 temp에 담아두었다가 head로써 반환

📌 결과

Accepted
Runtime 60ms (Beats 72.40%)
Memory 51.69MB (Beats 37.99%)

📚 러닝 포인트

처음에는 값을 서로 변경하려고 했다가 도저히 이 방법이 아닌 것 같아서 곰곰히 생각해 봤다. k가 length 보다 길 때를 뚫어져라 쳐다보니까 접근법은 노드 자체를, 그니까 next를 건들여서 변경해야하는 것 같았다. 그래서 결과의 head가 되야하는 노드를 미리 찾고, 그 전의 노드를 마지막 노드로 만들고 (next = null), 기존의 마지막 노드는 head를 가리키게 한다는 알고리즘을 생각해 냈다. 결국 cycle을 만들었다가 원하는 지점에서 끊는 방식인 거다. 근데 이번에도 빈 리스트를 미리 생각 못해서 제출 했다가 에러 나서 맨 처음에 예외 처리를 해주었다.