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 ) 以您想要的方式进行排序。