Вопрос от Microsoft и Amazon
Постановка проблемы Leetcode #25
Учитывая связанный список, переворачивать узлы связанного списка k за раз и возвращать его измененный список.
k — положительное целое число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конце должны оставаться как есть.
Пример:
Учитывая этот связанный список: 1->2->3->4->5
Для k = 2 вы должны вернуть: 2->1->4->3->5
Для k = 3 вы должны вернуть: 3->2->1->4->5
Примечание. Допускается только постоянная дополнительная память.
Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.
Шаг 1: Найдите длину списка
var findLength = function(list){ let count = 0; let p1 = list; let p2 = list; while(p2 && p2.next){ p1 = p1.next; p2 = p2.next.next; count++; } if(p2){ //If list had odd length count = count * 2 + 1; }else{ count *= 2; } return count; }
После нахождения длины нам нужно сохранить
let len = findLength(head);
Шаг 2: Если длина списка имеет равные k групп, это означает, что мы можем перевернуть и объединить их вместе. Предположим, что у нас нет k нет. узлов в последней группе мы должны сделать это по порядку.
Нам нужно найти точку, до которой она должна группироваться в обратном порядке, поэтому мы делаем следующий шаг.
let count = len - (len % k);
Если мы возьмем модуль len с k, мы сможем узнать, что если существует какая-либо группа, не имеющая k узлов.
Шаг 3: Создайте фиктивный указатель, который упростит проверку условий.
let result = new ListNode(0); let prev = result;
Таким образом, мы будем добавлять перевернутые k узлов с prevузлом
Шаг 4. Наша идея заключается в том, что нам нужно повторять до тех пор, пока не будет найдено количество допустимых групп.
while(head && count > 0){ let cur = head; //New k nodes reversed list let list = null; }
Шаг 5: Внутри цикла while нам нужно повторить k no. узлов и перевернуть, а затем добавить предыдущий узел.
while(head && count > 0){ let cur = head; let list = null; let flag = true; for(let i=0;i<k;i++){ count--; let temp = cur.next; if(!list){ cur.next = null; list = cur; }else{ cur.next = list; list = cur; } cur = temp; } prev.next = list; prev = head; head = cur; }
Для каждого реверса нам нужно уменьшить количество, и когда изначально у нас нет списка, мы можем назначить curlist, в противном случае нам нужно добавить его в начало.
После того, как k узлов перевернуты, нам нужно перевернуть еще один набор из k узлов вправо, поэтому нам нужен следующий указатель головы, поэтому,
let temp = cur.next; /*So we can use this temp *because we changed cur.next */ cur = temp;
Затем, после формирования каждой группы, нам нужно добавить к ней список result, чтобы
prev.next = list; prev = head; head = cur;
Таким образом, нашим следующим указателем головы будет cur, потому что нам нужно начать с этого места.
Шаг 6: Последний шаг предполагает, что если у нас есть группа узлов, отличных от k, мы должны добавить это также правильно, поэтому
if(head != null){ prev.next = head; } //Avoid dummy node return result.next;
Окончательный код:
Сложность времени:
O(n)Мы повторяем один за другим и меняем k узел на лету, а затем добавляем. Вычисление длины займет O(n/2)
Космическая сложность:
O(1) Мы не использовали никакого дополнительного пространства, кроме фиктивного узла