Сторнирование односвязного списка [Java]

Question

Мне было интересно, может ли кто-нибудь помочь объяснить, как перевернуть односвязный список без создания новых узлов или изменения данных в существующих узлах. Я пытаюсь подготовиться к финалу, и у нас был этот вопрос на предыдущем тесте. Они не публикуют ответы на части кода теста, и я не смог понять это.

Они сказали нам, что лучший способ обратить это вспять - это использовать «технику бегуна», которая, я думаю, я понимаю, что это такое. Они описали это как использование двух указателей или счетчиков, чтобы просмотреть список и собрать информацию, но я не уверен, как использовать это, чтобы полностью изменить список, который понравился. Я был в состоянии перебором кода, чтобы перевернуть список длиной 2, 3 и 4, но я не смог сделать цикл или сделать это рекурсивно. Спасибо за любой код или объяснение, как это сделать, спасибо.

Answer 1

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

void Reverse(List pList) {
   Reverse(pList, null, pList.First); // initial call
}

void Reverse(List pList, Node pPrevious, Node pCurrent) {
   if (pCurrent != null)
      Reverse(pList, pCurrent, pCurrent.Next);   // advance to the end

   else { // once we get to the end, make the last element the first element
      pList.First = pPrevious;
      return;
   }

   pCurrent.Next = pPrevious; // reverse the references on all nodes
} 

Answer 2

Вы можете получить код, начав с идеи просто - один за другим - выталкивать элементы из списка ввода и помещать их в изначально пустой список результатов:

NODE reverse(NODE list) {
  NODE result = null;
  while (list != null) {
    NODE head = <pop the first node off list>
    <push head onto result>
  }
  return result;
}

Результат будет обратным входу. Теперь замените Java на недостающие фрагменты

NODE reverse(NODE list) {
  NODE result = null;
  while (list != null) {
    // pop
    NODE head = list;
    list = list.next;
    // push
    head.next = result;
    result = head;
  }
  return result;
}

И все готово ...