Linked List | Rotate List

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

리스트를 k번 돌리라는 medium 난이도의 문제이다. 시계 반대방향으로 도는것인데, 맨 마지막 노드를 앞으로 가져오는 방식이다. 이 k는 노드 길이보다 더 길 수 있다. 예를들면, 5개 노드가 있는 리스트를 2 * 10^9회 돌라고 할 수 있다. 조건은 아래와 같다.

k의 값이 아주 크기때문에, 시키는대로 한번씩 돌면, 매우 효율적이지 않다. 그래서 나머지를 구하는 modulus(%) 를 이용한 해법을 구현했다. 솔루션은 아래와 같았다. 

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        int len = count(head);
        int newK = k % len;
        if (newK == 0){
            return head;
        }
        
        ListNode prev = new ListNode(-1);
        ListNode tail = prev;
        ListNode newHead = null;
        prev.next = head;
        for(int i = 0; i < newK; i++){
            tail = tail.next;
        }

        while(tail.next != null){
            tail = tail.next;
            prev = prev.next;
        }
        
        newHead = prev.next;
        prev.next = null;
        tail.next = head;
        
        return newHead;
    }
    
    public int count(ListNode node){
        int count = 0;
        while(node != null){
            node = node.next;
            count++;
        }
        return count;
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1)

 

count라는 함수를 구현해서, 리스트의 길이를 구한 후, 두개의 포인터를 이용해서 끝에서 k번째 떨어져있는 노드, 그리고 맨 마지막 노드를 찾아내어서 서로 가르키는 next값을 변형해서 풀어내었다. 이 해법으로 했을 때, 이미 100%의 속도를 달성했다. 전세계 100%라니! 하지만 스페이스는 48.14정도 쓰였다.

 

 

삐삐야 픽시야! 1273742 바퀴 돌도록 하자!

 

Reference

https://leetcode.com/problems/rotate-list/

Rotate List - LeetCode