61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example, given 1 → 2 → 3 → 4 → 5 → NULL and k = 2,

return 4 → 5 → 1 → 2 → 3 → NULL.

61. Вращение списка

Задан список. Поверните список циклически на k позиций вправо (k неотрицательно).

Например, если задан список 1 → 2 → 3 → 4 → 5 → NULL, а k = 2,

то после вращения получим 4 → 5 → 1 → 2 → 3 → NULL.

class Solution {

public:

ListNode* rotateRight(ListNode* head, int k) {

}

};

РЕШЕНИЕ

последовательности

Анализ алгоритма

Если список пустой или k = 0, то возвращаем голову.

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

Ищем голову нового списка, установим на нее указатель q. Также установим указатель p на предыдущий ей элемент.

Устанавливаем p → next = NULL.

Совершим присваивание p = q.

Двигаем указатель q до конца, пока он не будет указывать на последний элемент списка (пока q → next не станет равным NULL).

Остается q → next присвоить head. Головой результирующего списка является p.

Реализация алгоритма

class Solution

{

public:

ListNode* rotateRight(ListNode* head, int k)

{

if ((head == NULL) || (k == 0)) return head;

ListNode *p = head;

int len = 0;

while(p != NULL)

{

p = p->next;

len++;

}

if (k % len == 0) return head;

k = k % len;

p = head;

for(int i = 0; i < len - k - 1; i++)

p = p->next;

ListNode *q = p->next;

p->next = NULL;

p = q;

while(q->next != NULL)

q = q->next;

q->next = head;

return p;

}

};