Возникли проблемы с рекурсивным вызовом метода вставки заказа для сортировки всего связанного списка

Question

У меня есть метод сортировки Ordered Insertion, который сортирует элемент в связанном списке по возрастанию по мере его добавления.

 //getData() returns the data in that Node
 //getLink() returns the link to the next Node
 //setLink() sets the link of the Node 
 //top is the reference to the first node

public void ordInsert(int newItem) {

 IntNode prev = null;
 IntNode next = top;
 while(next!=null && next.getData()<newItem){
   prev = next;
   next = next.getLink();
 }
 IntNode newNode = new IntNode(newItem,next);
 if(prev==null)
   top = newNode;
 else
   prev.setLink(newNode);
}

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

  public void inSort(){

     IntNode next = top;

     if(next != null){

       ordInsert(next.getData());
       top.setLink(next.getLink());
       inSort();
     }

   return;
 }

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

 Input: 3000 400 40 120 70 
 Expected Output : 40 70 120 400 3000

Answer 1

Отслеживание бесконечной рекурсии

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

Давайте посмотрим наПример ввода, который вы предоставили:

Input: 3000 400 40 120 70

В начале top указывает на узел 3000.В inSort, next устанавливается в точку, где top указывает, а 3000 - значение для вставки.

При вызове ordInsert, начальное условие

while(next!=null && next.getData()<newItem)

равно никогда true, потому что next.getData() всегда равно newItem (это тот самый объект, который вы пытаетесь повторно вставить!).Как следствие, узел top воссоздается и вставляется в верхнюю часть, а top соответственно устанавливается там.Таким образом, список теперь:

3000 3000 400 40 120 70

с top, указывающим на первый элемент.

, поскольку next является ссылкой на тот же объект, что и top, * 1036Ссылка * s теперь установлена ​​на 3000 рядом с ней.И вы попадаете в ту же ситуацию, что и раньше, другой элемент предшествует только списку.

Повторный вызов inSort() будет повторять этот процесс бесконечно, чтобы получить результат

3000 3000 ... 3000 400 40 120 70

---

Проблемы

• Вставляемые элементы не удаляются, что приводит к расширению списка
• Сброс top в inSort делает недействительнымипредпосылка для цикла while в ordInsert.

Предлагаемое решение

Метод ordInsert работает, только если список, в который вставляется новый элемент, уже отсортирован.Итак, стратегия должна быть такой:

1. Detach element at index 0
2. Sort remaining list
3. insert detached element into sorted list

Таким образом, сначала сохраните ссылку на верхнюю часть списка, затем переместите маркер top на следующий элемент и установите для отсоединенного (предыдущий верхний) элемента значениеуказать на null.Это не сделает недействительной предпосылку цикла while, поскольку top все еще ссылается на верхнюю часть списка (элемент с индексом 0 был удален из списка).

Затем позвоните inSort() из сокращенного списка.После успешного вызова используйте ordInsert() для вставки отдельного элемента.Лучше всего заставить его работать с IntNode, а не создавать совершенно новый элемент.

Для рекурсии работайте, утверждая, что top ссылается на начало списка (укороченный [после отсоединения] или расширенный [после повторной вставки]), так что для любого шага рекурсии состояние программы будет действительным.И остерегайтесь базового случая, когда top == null.

Answer 2

В inSort условие останова if(next == null).next - это top, а top - заголовок списка (не последний узел).Поэтому рекурсия никогда не прекращается.

Кроме того, вместо сортировки существующего связанного списка , вы вставляете новые данные , код дублирует бесконечность узлов.