61. Rotate List.txt

//Просто совет: всякий раз, когда вы видите смену позиций типа вращения, помните, что это шаблон, и его можно использовать для оптимизации вашего кода. В этом случае вам не 
//нужно каждый раз считать k вращений, вам просто нужно рассчитать k%n вращений, где n — количество узлов. пройти весь связанный список один раз лучше, чем выполнить k 
//поворотов, когда k очень велико.

//Оптимальный код. Проходим все узлы списка, замыкаем конечный узел на первый, ищем новую голову и хвост. 

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return head;
        
        int len=1; // количество узлов
        ListNode *newH, *tail;
        newH=tail=head;
        
        while(tail->next)  // получить количество узлов в списке
        {
            tail = tail->next;
            len++;
        }
        tail->next = head; // замыкаем последний узел списка на первый узел списка

        if(k %= len) 
        {
            for(auto i=0; i<len-k; i++) tail = tail->next; // Хвостовой узел - это (len-k)-й узел (1-й узел - головной)
        }
        newH = tail->next; //Новое начало списка = следущему списку, после конечного элемента
        tail->next = NULL; //В последнем элементе объевляем NULL в next
        return newH;
    }
};




//Мой код. 3 цикла. 1-ый добавляет все узлы в вектор, 2-ой выставляет их в правельный порядок, 3-ий связывает узлы в новый порядок.
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL) return head;
        vector<ListNode*> allNodes;
        ListNode *temp = head;	
        while (temp != NULL) {
            allNodes.push_back(temp);
            temp = temp->next;
        }
        int startPos = k % allNodes.size();				//Подсчёт на какой позиции окажется первый узел.
        for (int i = 0; i < startPos; i++){
            allNodes.insert(allNodes.begin(), allNodes.back());
            allNodes.erase(allNodes.begin() + allNodes.size() - 1);
        }
        temp = allNodes[0];
        for (int i = 1; i < allNodes.size(); i++) {
            temp->next = allNodes[i];
            temp = temp->next;
        }
        temp->next = NULL;
        return allNodes[0];
    }
};