Учитывая head односвязного списка, сгруппируйте вместе все узлы с нечетными индексами, за которыми следуют узлы с четными индексами, и верните переупорядоченный список.
Первый узел считается нечетным, второй узел считается четным и так далее.
Обратите внимание, что относительный порядок внутри как четных, так и нечетных групп должен оставаться таким же, как и во входных данных.
Вы должны решить задачу в O(1) дополнительной пространственной сложности и O(n) временной сложности.
Пример 1:
Input: head = [1,2,3,4,5] Output: [1,3,5,2,4]
Решение:
В данной задаче нам необходимо разделить нечетные и четные проиндексированные элементы связного списка.
В этом случае нам нужно проверять только индексы, а не значения элементов.
Мы должны рассматривать головной узел как нечетный индекс. Итак, сначала мы проверим, что заголовок null или список пуст.
if(head == 0)
return NULL;
Теперь мы создадим две новые переменные, нечетные и четные.
Переменная нечетная будет указывать на голову, а переменная четная будет указывать на следующий узел головы, что означает второй элемент связанного списка.
ListNode* odd = head; ListNode* even = head -> next;
Нам также нужна переменная для отслеживания нашей четной переменной. Для этого мы создадим еще одну переменную, evenBegin. Эта переменная будет отслеживать начало четных индексированных элементов.
ListNode* evenBegin = even;
Теперь поставим условие, чтобы нечетные и четные переменные не были нулевыми.
Если условие выполняется, мы свяжем нечетный со следующим нечетным индексированным элементом и четный со следующим четным индексированным элементом.
И оба, нечетные и четные, будут увеличены.
while(odd -> next && even -> next)
{
odd -> next = odd -> next -> next;
even -> next = even -> next -> next;
odd = odd -> next;
even = even -> next;
}
Теперь мы должны поместить evenBegin в конец списка после нечетного.
odd -> next = evenBegin;
Последний шаг — вернуть голову связанного списка.
return head;
Ниже приведена полная реализация задачи:
Спасибо за прочтение!
S.
