Java Splitting integer Связанный список

Question

Мне нужно написать метод, который начинается с единственного связанного списка целых чисел и специального значения, называемого значением расщепления. Элементы списка не имеют особого порядка. Метод делит узлы на два связанных списка: один содержит все узлы, которые содержат элемент, меньший, чем значение разделения, и один, который содержит все остальные узлы. Если в исходном связанном списке есть повторяющиеся целые числа (т. Е. Любые два или более узла с одним и тем же элементом в них), то новый связанный список, который имеет этот элемент, должен иметь такое же количество узлов, которые повторяют этот элемент. Метод возвращает два заголовка - по одному для каждого из связанных списков, которые были созданы.

Я провел много часов, пытаясь понять это, и думаю, что это самое близкое, но у меня есть ошибка при компиляции, что мой экземпляр CopyTail * IntNodes не может быть инициализирован. Я также могу ошибаться в своем коде .... Любая помощь, указывающая на меня в правильном направлении?

public static IntNode[ ] listSplitLessGreater(IntNode source, int splitter) 
{ 
    IntNode copyHeadLess; 
    IntNode copyTailLess; 
    IntNode copyHeadGreater; 
    IntNode copyTailGreater; 
    IntNode[ ] answer = new IntNode[2]; 
    boolean less = true; 
    boolean greater = true; 

    // Handle the special case of the empty list. 
    if (source == null) 
    return answer; // The answer has two null references . 

    //Split list into two lists less and greater/equal than splitter.  
    while (source.link != null) 
    { 
    if (splitter < source.data) 
     { 
      if (less) 
      { 
      copyHeadLess = new IntNode(source.data, null); 
      copyTailLess = copyHeadLess; 
      less=false; 
      } 
      else 
      { 
      source = source.link; 
      copyTailLess.addNodeAfter(source.data); 
      copyTailLess = copyTailLess.link; 

      } 
     } 
     else 
     { 
      if (greater) 
      { 
      copyHeadGreater = new IntNode(source.data, null); 
      copyTailGreater = copyHeadGreater; 
      greater=false; 
      } 
      else 
      { 
      source = source.link; 
      copyTailGreater.addNodeAfter(source.data); 
      copyTailGreater = copyTailGreater.link; 

      } 
     } 

    }  

    //Return Head References 
    answer[0] = copyHeadLess; 
    answer[1] = copyHeadGreater; 

    return answer; 

}

Answer 1

Я думаю, что вы делаете его более сложным, чем это должно быть, путем моделирования список только с одним классом (IntNode). Если вы моделируете его как «список» и «узел в списке», тогда легко получить пустой список. Вам также не нужно отслеживать как голову, так и хвост - список может это сделать. В этот момент, это очень просто:

• Создайте два пустых список, один для «нижнего» и один для «не ниже»
• перебрать исходный список:
  • Поработает, какой список, чтобы добавить элемент для
  • Добавьте элемент
• Вернись оба списка (например, используя массив, как вы сделали)

Обратите внимание, что даже без этого вы можете сделать свой код проще, просто используя null, чтобы обозначить «У меня еще нет списка». На данный момент ваш код не будет компилироваться, так как copyHeadLess и т. Д. Не являются определенно присвоены, когда они используются. Вы,, знаете, что вы не будете пытаться использовать их до тех пор, пока они не будут назначены, но компилятор этого не делает. Я бы по-прежнему рекомендовал подход к ремоделированию: :)

Answer 2

Если источник не равен null, но source.link имеет значение null (список состоит только из одного элемента), то вы никогда не присваиваете своим переменным copyHeadLess и т. Д. Попробуйте инициализировать их до нуля или по умолчанию:

IntNode copyHeadLess = null; 
    IntNode copyTailLess = null; 
    IntNode copyHeadGreater = null; 
    IntNode copyTailGreater = null; 
    IntNode[ ] answer = new IntNode[2]; 
    boolean less = true; 
    boolean greater = true; 

    // Handle the special case of the empty list.  
    if (source == null) 
    return answer; // The answer has two null references . 

    //Split list into two lists less and greater/equal than splitter.  
    while (source.link != null) 
    { 
    // what about case where source isn't null but source.link is null? 
    }  

    //Return Head References 
    answer[0] = copyHeadLess; // this may have never been assigned in your original code 
    answer[1] = copyHeadGreater; // this may have never been assigned in your original code 

    return answer; 

}