java - 为什么我的链表的排序方法不起作用？

Question

我正在尝试实现单链表的排序方法。该方法假设遍历列表，比较一对节点，并在需要时将其中一个放在前面。它使用另外两种方法: -Remove()(从列表中删除特定节点) - InsertFront()(在列表的前面插入一个新节点。 这两种方法都可以单独工作并且一切都可以编译。

    public Link remove(String lastName)
{
    Link current_ = first_;
    Link prior_ = null;
    Link found_ = null;
    while (current_ != null && current_.lastName.compareTo(lastName) != 0)
    {
        prior_ = current_;
        current_ = current_.next;
    }
    if(current_ != null)
    {
        if(prior_ == null)
        {
            found_ = first_;
            System.out.println(current_.next.lastName);
            first_ = current_.next;
        }
        else if(current_ == last_)
        {
            found_ = last_;
            Link hold_ = first_;
            first_ = prior_;
            first_.next = current_.next;
            first_ = hold_;
        }
        else
        {
            found_ = current_;
            Link hold_ = first_;
            first_ = prior_;
            first_.next = current_.next;
            first_ = hold_;
        }
    }
    return found_;
}

    public void insertFront(String f, String m, String l)
{
    Link name = new Link(f, m, l);
    if (isEmpty())
    {
        System.out.println("Adding first name");
        first_ = name;
        last_ = name;

    }
    else
    {
        System.out.println("Adding another name");
        Link hold_ = first_;
        first_ = last_;
        first_.next = name;
        last_ = first_.next;
        first_ = hold_;
    }
}

我尝试修复它，但总是遇到两个不同的问题:

1. 它可以工作，但不会将链接重新插入。

       public void Sort()
   {
   Link temp_;
   boolean swapped_ = true;
   while (swapped_ == true)
   {
       swapped_ = false;
       Link current_ = first_;
       String comp_ = current_.lastName;
   
       while (current_ != null && current_.lastName.compareTo(comp_) >= 0)
       {
           current_ = current_.next;
       }
   
       if (current_ != null)
       {
           temp_ = remove(current_.lastName);
           insertFront(temp_.firstName, temp_.middleName, temp_.lastName);
           swapped_ = true;
       }
     }
   }
   

2. 我收到空指针异常。

   Exception in thread "main" java. lang. NullPointerException
   at List $ Link . access $000(List . java : 25)
   at List . Sort ( List . java:165)
   at main( java :79)
   

   Java 结果:1

调试结果:

Listening on javadebug
Not able to submit breakpoint LineBreakpoint LinearGenericSearch.java : 28, reason: The breakpoint is set outside of any class.
Invalid LineBreakpoint LinearGenericSearch.java : 28
User program running
Debugger stopped on uncompilable source code.
User program finished


    public void Sort()
        Link temp_;     
    boolean swapped_ = true;
    while (swapped_ == true)
    {
            Link current_ = first_;
            swapped_ = false;
            while (current_.next != null)
            {

                if((current_.lastName.compareTo(current_.next.lastName)) > 0)
                {
                    temp_ = remove(current_.next.lastName);
                    insertFront(temp_.firstName, temp_.middleName, temp_.lastName);
                    swapped_ = true;
                }
                current_ = current_.next;
            }
        }
    }

我的问题是:我做错了什么？关于如何避免下次出现这种情况有什么建议吗？

Answer 1

在 Java 中，你不必手动完成所有这些!只需使用 LinkedList，代码即可

 compareTo() 

通过实现

 Comparable Interface

( http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html ) 并调用

 Collections.sort(List list, Comparator c) 

( http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html ) 按照您想要的方式排序。