[LeetCode] 61. Rotate List, Medium

1. 문제

• 단일 연결리스트와 정수 k가 주어질 때, k만큼 오른쪽으로 회전한 리스트를 반환하라.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if(!head) return head
    let length = 1;
    
    let p1 = head;
    
    while(p1.next) {
        length++;
        p1 = p1.next;
    }
        
    p1.next = head;
    
    for(let i = 0; i < length - (k % length); i++) {
        p1 = p1.next
    }

    head = p1.next;
    p1.next = null;

    return head;
    // let length = 0;
    
    // let p1 = head;
    
    // while(p1) {
    //     length++;
    //     p1 = p1.next;
    // }
        
    // for(let i = 0; i < k % length; i++) {
    //     p1 = head;

    //     while(p1 && p1.next && p1.next.next) {
    //         p1 = p1.next;
    //     }
        
    //     p1.next.next = head;
    //     head = p1.next;
    //     p1.next = null;
    // }
       
    // return head;
};

• 일단 k가 리스트 길이 이상 반복되는 경우, 동일한 형태가 나오기 때문에 전체 리스트 길이를 구하고, k와 나머지를 구해 해당 수 만큼 반복문을 돌며 노드를 이동시키는 걸 고안했다.
• 더 나은 풀이 방식은 내가 떠올리지 못한, 마지막 노드를 찾고 해당 노드를 어떻게 head로 보낼 지 고민한 부분을 해소해줬다.
• length - k % length를 하면, 마지막 노드 부터 몇 번째 노드 까지 앞으로 이동할 것인지 알 수 있고, 그에 맞게 head와 next를 업데이트 해준다.