[LinkedList][Medium] 61. Rotate List

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

 

 

Q 주어진 리스트를 k 회 회전하라. 

 

 

Solution

 회전의 결과는 우선, 뒤에서 k 번째 노드를 찾아서 해당 노드를 head로 만들면 된다. 

 

 따라서 뒤에서 k 번째 노드를 찾고 새로운 head로 만든다. 

 기존 list의 tail 노드의 next를 기존 head에 연결한다. 

 k번째 노드의 앞노드는 새로운 tail 이 되므로 next를 null로 set 한다. 

 

 따라서 기본적으로 뒤에서 k 번째 노드를 찾는 문제와 매우 유사. 

 

 다만, k 가 리스트 길이보다 긴 경우, 리스트 길이로 정규화를 먼저 한다.

 

 코드 

 

public ListNode RotateRight(ListNode head, int k) 
{
    if(head == null)
        return head;

    // count list.
    int cnt = 0;
    ListNode node = head;
    while(node != null)
    {
        ++cnt;
        node = node.next;
    }
    k %= cnt;
    if(k == 0)
        return head;

    // find the kth node from the tail.
    ListNode fast = head;
    node = head;
    ListNode prev = null;
    ListNode tail = null;
    cnt = 0;
    while(fast != null)
    {
        if(cnt >= k)
        {
            prev = node;
            node = node.next;
        }
        tail = fast;
        fast = fast.next;
        cnt++;
    }
    
    // prev - tail.
    // node - new head.
    prev.next = null;
    tail.next = head;
    return node;
}

 

 적당한 결과.