首页 文章

Java拆分整数链表

提问于
浏览
2

我需要编写一个方法,该方法以单个链接的整数列表和一个称为拆分值的特殊值开头 . 列表的元素没有特定的顺序 . 该方法将节点划分为两个链接列表:一个包含所有包含小于拆分值的元素的节点,另一个包含所有其他节点 . 如果原始链表具有任何重复的整数(即,其中具有相同元素的任何两个或更多个节点),则具有该元素的新链表应具有重复该元素的相同数量的节点 . 该方法返回两个头引用 - 每个引用创建一个链接列表 .

我花了无数个小时试图做到这一点,并认为这是最接近但我编译时我的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;

}

2 回答

  • 3

    通过使用单个类( IntNode )建模列表,我认为你使它变得比它需要的更复杂 . 如果您将其建模为"the list"和"a node in the list",那么很容易有一个空列表 . 你也很简单:

    • 创建两个空列表,一个用于"lower",另一个用于"not lower"

    • 迭代原始列表:

    • 确定要添加元素的列表

    • 添加元素

    • 返回两个列表(例如,使用已完成的数组)

    请注意,即使没有它,只需使用 null 表示"I haven't got this list yet"即可使代码更简单 . 目前您的代码无法编译,因为 copyHeadLess 等在使用时并未明确分配 . You 知道你赢了't try to use them until they'已被分配,但编译器没有't. I'仍然建议重建方法虽然:)

  • 2

    如果source不为null,但source.link为null(list仅由一个元素组成),那么您永远不会为copyHeadLess等分配变量 . 尝试将它们初始化为null或默认值为:

    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; 
    
     }
    

相关问题