[leetcode] Rotate List

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

Rotate List - LeetCode

우선 문제부터 간단하게 요약하면,

 

single linked list를 k회 회전 시켰을 때의 head를 출력해야 하는 문제입니다. 

 

<Solution>

O(n)의 시간복잡도로 충분히 해결할 수 있습니다. 

우선 single linked list의 head는 총 node의 갯수를 알아야 하므로 1회 전체를 순회 해야합니다.

해당 과정 이후에는 몇번째 node가 head로 출력되어야 하는지를 알 수 있기 때문에, 해당 node까지 찾아가서, return을 시켜주면 됩니다. 

 

조금 주의해야하는 점은 처음 상태가 circular로 순회하는 상태가 아니기 때문에 처음에 tail의 next node로 head를 지정해놓고 나중에 끊어 주는 방식의 구현이 편리합니다. 

 

실제 구현은 아래와 같습니다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // if empty return null
        if(head == nullptr || head->next == nullptr) return head;

        // connect head and tail
        // make tail's next node is head
        ListNode* curHead = head;
        ListNode* curNode = head;
        int nodeCnt = 1;
        while(curNode->next){
            curNode = curNode->next;
            nodeCnt++;
        }
        // cur node = tail
        curNode->next = curHead;
        
        curNode = curHead;
        for(int i = 0; i<nodeCnt - k%nodeCnt -1 ; i++){
            curNode = curNode->next;
        }
        curHead = curNode->next;
        curNode->next = nullptr;

        return curHead;

    }
};