Leetcode - 61. Rotate List

문제

주어진 링크드 리스트를 k 번 rotate시켜라.

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

해결 O(N^2)

한번 rotate하는건 쉽다. 링크드리스트의 맨 마지막 노드 (node), 그리고 직전노드 prev라고 할때, 아래와 같이 하면된다.

        prev->next = NULL;
        node->next = head;
        head = node;

이걸 k 번반복. 총 시간복잡도는 O(N^2)가 된다.
역시나 TLE 발생 (12 / 231 test cases passed.)

struct ListNode* rotateRight(struct ListNode* head, int k){
    struct ListNode *node = head, *prev = NULL;
    for (int i = 0; i < k; i++) {
        for (; node && node->next; prev = node, node = node->next)
            ;
        if (!prev)
            break;
        prev->next = NULL;
        node->next = head;
        head = node;
    }
    return head;
}

해결 O(N)

생각해보면 전체 k번 rotate할 필요가 없다. 참고로 k가 될수 있는 값은 매우 크다(0 <= k <= 2 * 10^9). 리스트의 크기 이하 번만 rotate할수 있게 계산이 가능하다. head_pos = list_size - (k % list_size); 이렇게 새로운 head가 될 노드의 위치를 계산할 수 있다.

그리고 첫번째 해결방법처럼 맨 마지막 노드tail을 찾아서 이전 head를 가리키게 하면 된다.

    prev->next = NULL;
    tail->next = head;
    head = node;

결과는 100% faster 가 나왔음.

struct ListNode* rotateRight(struct ListNode* head, int k){
    struct ListNode *node = head, *prev = NULL, *tail = NULL;
    int list_size = 0;
    int head_pos = 0;
    
    /* get list size */
    for (; node; prev = node, node = node->next)
        list_size++;
    if (list_size == 0 || list_size == 1)
        return head;
    
    /* initialize the position and nodes */
    head_pos = list_size - (k % list_size); //FIXME div by 0
    if (head_pos == list_size)
        return head; /* no need to rotate */
    tail = prev;
    node = head;
    prev = NULL;
    
    /* ratate by head_pos */
    for (int i = 0; i < head_pos; i++, prev = node, node = node->next)
        ;
    prev->next = NULL;
    tail->next = head;
    head = node;
    return head;
}

 o -> o -> o -> o -> o -> o -> NULL
head      prev node      tail