Вопрос от 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) Мы не использовали никакого дополнительного пространства, кроме фиктивного узла