Обратные узлы в k-группе

Question

Учитывая этот связанный список: 1-> 2-> 3-> 4-> 5 k = 2, вы должны вернуть: 2-> 1-> 4-> 3-> 5 Я не получаю желаемый результат, может какой-тоодин посмотрел, где я делаю ошибку.

`class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    } }


class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
       push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;

    } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;}


  reverseKGroup (head,k){  
  var count = 0;
  var  now =  head;
  var last = head;
  var tmp = null;

  if (!head || k < 2) return head;  
  while (now && count < k) {
    now = now.next;
    count++;
  }

  if (count === k) {
    reverseKGroup(this.now, k);
    while (count-- > 0) {
      tmp = last.next;
      last.next = now;
      now = last;
      last = tmp;
    }
    last = now;
  I need to implement interview problem , 

Учитывая этот связанный список: 1-> 2-> 3-> 4-> 5

k = 2, вы должны вернуть:2-> 1-> 4-> 3-> 5
Я не получаю желаемого результата, может кто-то посмотрел, где я делаю ошибку.

class Node{
        constructor(val){
            this.val = val;
            this.next = null;
        } }


    class SinglyLinkedList{
        constructor(){
            this.head = null;
            this.tail = null;
            this.length = 0;
        }
           push(val){
            var newNode = new Node(val);
            if(!this.head){
                this.head = newNode;
                this.tail = this.head;

        } else {
                this.tail.next = newNode;
                this.tail = newNode;
            }
            this.length++;
            return this;}


      reverseKGroup (head,k){  
      var count = 0;
      var  now =  head;
      var last = head;
      var tmp = null;

      if (!head || k < 2) return head;  
      while (now && count < k) {
        now = now.next;
        count++;
      }

      if (count === k) {
        reverseKGroup(this.now, k);
        while (count-- > 0) {
          tmp = last.next;
          last.next = now;
          now = last;
          last = tmp;
        }
        last = now;
      }
        console.log(last);
      return last;}

     }

Answer 1

Хитрость заключается в том, чтобы сначала получить длину списка, а затем использовать ее, чтобы определить, какой элемент будет первым в повернутом списке. Отсюда тривиально построить повернутый список.

Индекс первого элемента повернутого списка - это просто длина списка по модулю k , где k - количество вращений. Преобразуйте связанный список в простой старый массив Javascript, чтобы получить его длину, и вы готовы к гонкам:

var rotateRight = function(head, k) {
    // if empty list, do nothing
    if (!head) {
        return head;
    }

    // determine actual number of rotations
    let array = toArray(head);
    let length = array.length;
    let rotations = k % length;

    // if no rotations are required, return the original list
    if (rotations == 0) {
        return head;
    }

    let newHead = null;
    let first = null;

    // construct the rotated list
    for(let i = 0; i < length; i++) {
        let index = ((length - rotations) + i) % length;
        let temp = new ListNode(array[index]);

        if (newHead) {
            newHead.next = temp;
        }
        else {
            first = temp;
        }

        newHead = temp;
    }

    return first;
};

// converts the linked list to an array so that we can find the length easily
function toArray(head) {
    let array = [];

    while(head) {
        array.push(head.val);
        head = head.next;
    }

    return array;
}

(я уверен, что есть рекурсивное решение, которое является более эффективным / элегантнымчем это, но это работает)

Протестировано на LeetCode: