Технические интервью: сдвиг связанного списка

(Решение в JavaScript)

В заданном связанном списке сдвиньте все элементы на k позиций и верните его новый заголовок.

Сдвиг связанного списка означает перемещение его узлов вперед или назад и перенос их вокруг списка, где это необходимо. Перемещаются ли узлы вперед или назад, определяется тем, является ли k положительным или отрицательным.

Вы можете предположить, что у связанного списка всегда будет хотя бы один узел (голова никогда не будет null ).

// Input: head = 0 -> 1 -> 2 -> 3 -> 4 -> 5
//        k = 2

// Expected output: 4 -> 5 -> 0 -> 1 -> 2 -> 3

Решение

Во-первых, давайте создадим все необходимые переменные.

function shiftLinkedList(head, k) {

  // variable i to traverse through the Linked List to shift it
  let i = 0;

  // variable c to count the amount of elements
  let c = 1;

  // variable node for the current node while traversing through the Linked List
  let node = head;
  
  // variable newNode to store the value of the head of the shifted Linked List
  let newHead = head;

  // variable last to store the value of the last node of the shifted Linked List
  let last = head;
}

Прежде чем сдвинуть связанный список, мы должны посчитать его длину. Для этого давайте создадим цикл while, который будет увеличивать значение c на единицу с каждым циклом, пока значение внешнего узла не станет равным null.

function shiftLinkedList(head, k) {

  let i = 0;
  let c = 1;
  let node = head;
  let newHead = head;
  let last = head;

  // while node.next doesn't equal null
  while (node.next) {
    // reassign the value of variable node to the next node
    node = node.next;
    // increase the value of c by 1
    c++;
  }

  // after while loop, reassign the value of variable node to head again
  node = head;

}

Чтобы не сдвигать элементы на несколько циклов, если k больше длины связанного списка, найдем модуль.

function shiftLinkedList(head, k) {

  let i = 0;
  let c = 1;
  let node = head;
  let newHead = head;
  let last = head;

  while (node.next) {
    node = node.next;
    c++;
  }

  node = head;

  // find module k of c
  k %= c;

}

Если k равно 0, это означает, что связанный список не должен сдвигаться.

function shiftLinkedList(head, k) {

  let i = 0;
  let c = 1;
  let node = head;
  let newHead = head;
  let last = head;

  while (node.next) {
    node = node.next;
    c++;
  }

  node = head;

  k %= c;

  // if parameter k is equal 0
  if (k === 0) {
    // return head of given Linked List
    return head;
  }
}

Давайте создадим еще один цикл while, который проходит через связанный список и находит последний элемент сдвинутого связанного списка.

function shiftLinkedList(head, k) {

  let i = 0;
  let c = 1;
  let node = head;
  let newHead = head;
  let last = head;

  while (node.next) {
    node = node.next;
    c++;
  }

  node = head;

  k %= c;

  if (k === 0) {
    return head;
  }

  // while node.next doesn't equal null
  while (node.next) {
    // reassign the value of variable node to the next node
    node = node.next;
    // increase the value of i by 1
    i++;

    // while k is positive and i is bigger than k
    if (k > 0 && i > k) {
      // reassign the value of the last node to the next node of the previous 'last'
      last = last.next;
    }

    // if k is negative and sum of k and i is equal -1
    if (k < 0 && i + k === -1) {
      // assign value of the 'last' to current node
      last = node;
    }
  }
}

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

function shiftLinkedList(head, k) {

  let i = 0;
  let c = 1;
  let node = head;
  let newHead = head;
  let last = head;

  while (node.next) {
    node = node.next;
    c++;
  }

  node = head;

  k %= c;

  if (k === 0) {
    return head;
  }

  while (node.next) {
    node = node.next;
    i++;

    if (k > 0 && i > k) {
      last = last.next;
    }

    if (k < 0 && i + k === -1) {
      last = node;
    }
  }

  // the next element of 'last' becomes a new head of shifted Linked List
  newHead = last.next;
  
  // the head of the original Linked List becomes the next element of the last one from the original Linked List
  node.next = head;

  // assign the next element of the last one from the shifted Linked List to null
  last.next = null;

  // return head of the shifted Linked List
  return newHead;

}

Вы можете узнать больше о Linked List in JavaScript по ссылке ниже: