61. Rotate List

문제 개요

leetcode 의 Rotate List 문제로 linked list 가 주어지면 k 의 수 만큼 오른쪽으로 head 를 옮겨야 한다.

 

예를 들어 아래와 같은 linked list 가 있고 k = 2 일때는 아래와 같다.

k=0) 1 -> 2 -> 3 -> 4 -> 5 -> nil

k=1) 5 -> 1 -> 2 -> 3 -> 4-> nil

k=2) 4 -> 5 -> 1 -> 2 -> 3-> nil

 

문제 풀이

문제의 제약조건을 보면 k 의 수가 최대 20억 이하까지 나올 수 있다.

단순 반복문으로 풀면 당연히 시간 초과할것 같았지만 처음에는 신경쓰지 않고 풀었다.

당연히 특정 테스트케이스에서 시간 초과가 났다.

 

해당 문제는 배열이 아닌 linked list 문제이기 때문에 원소의 개수를 구하기 위해서 linked list 를 한번 모두 순회해야 한다.

전체 원소의 수(count)를 알면 k 를 전체 원소의 수(count)로 나눈 나머지값 만큼만 반복하면 문제가 풀린다.

 

왜 k = k % count 처럼 전체 원소의 수만큼 나눈 나머지만 돌리면 될까?

간단히 생각하면 쉽다.

만약, 3개의 원소가 있고 k=3,6,9,12 등 원소의 수와 같은 3의 배수인 경우에는 원소를 돌리지 않아도 된다.

3%3=0, 6%3=0, 9%3=0 처럼 k 는 0이 되는것을 알 수 있기 때문에 원소의 수 만큼 나눈 나머지 값만큼만 순회해도 문제가 풀리게 된다. 

문제 코드

    public static ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;

        int count = 0;
        ListNode node = head;
        while(node != null) {
            node = node.next;
            count++;
        }

        k %= count;
        for(int i=0; i<k; i++) {
            ListNode cur = head;
            ListNode prev = null;

            while(cur != null && cur.next != null) {
                prev = cur;
                cur = cur.next;
            }

            cur.next = head;
            prev.next = null;
            head = cur;
        }

        return head;
    }

 

1. cur, prev 포인터를 이용한다.

cur 포인터는 head 와 같은 노드를 보고, prev 는 cur 의 이전 노드를 보도록 처음에는 null 값을 할당한다.

반복문을 순회하며 cur 은 마지막 노드를, prev 는 cur 의 바로 이전 노드를 보도록 한다.

 

2. while 순회가 완료되었으면,

cur.next = head 로 마지막 노드는 첫번째 노드를 가리키도록 하고,

prev.next = null 로 바로 이전 노드였던 prev 노드가 가장 마지막 노드가 된다.

head = cur 로 head 노드를 cur 을 바라보게 하여 마지막 노드가 첫번째 노드가 되도록 한다.

 

3. 1번과 2번 로직을 k %= count 만큼 돌려서 문제를 해결한다.

위 1번과 2번 로직은 k 의 수를 전체 원소의 수를 나눈 나머지 만큼만 돌리면 문제를 해결할 수 있다.

 

 

시간/공간 복잡도

시간복잡도 : O(n) + @

공간복잡도 : O(1)