طريقة الفرز للقائمة المرتبطة بشكل مضاعف

Question

في محاولة لمعرفة كيفية فرز قائمتي المرتبطة بشكل مضاعف.أحصل على استثناء مؤشر فارغ هنا:

while (temp.getNext()!=null){

هل هناك نهج أفضل أو أي نصيحة للحصول على هذا تسير في الطريق الصحيح?

public void sort() {
    //bubble sort!
    boolean swapped = (head != null);
    while (swapped) {
        swapped = false;

        EntryNode temp = head;

        //can't swap something with nothing
        while (temp.getNext()!=null){
            if (temp.getLastName().compareTo(temp.getNext().getLastName()) > 0) {
                swapped = true;

                //special case for two nodes
                if (size == 2) {
                    //reassign head and tail
                    tail = temp;
                    head = temp.getNext();
                    tail.setPrev(head);
                    head.setNext(tail);
                    tail.setNext(null);
                    head.setNext(null);
                }
                //if swapping is at head
                else {

                    if (temp == head) {
                        head = temp.getNext();
                        temp.setNext(head.getNext());
                        head.getNext().setPrev(temp);
                        head.setPrev(null);
                        head.setNext(temp);
                        temp.setPrev(head);
                    }

                    else {
                        temp.setNext(temp.getNext().getNext());
                        temp.setPrev(temp.getNext());
                        temp.getNext().setNext(temp);
                        temp.getNext().setPrev(temp.getPrev());
                    }
                }
            }
            //loop through list
            temp = temp.getNext();
        }
    }
}

Answer 1

استخدم دمج فرز الخوارزمية، غالبا ما يكون أفضل خيار لفرز قائمة مرتبطة (واحدة أو مضاعفة).هناك بالفعل نشر مناقشة مشاكل التنفيذ ذات الصلة.

Answer 2

أعتقد أنك يجب أن تحقق ل:

while(temp != null)

لأنك تقوم بالفعل بتعيين

temp = temp.getNext()

في نهاية while حلقة.

Answer 3

النهج البسيط هو وضع محتويات القائمة في صفيف ، واستخدام Arrays.sort لفرز المصفوفة ، وأخيرا إعادة بناء القائمة من المصفوفة التي تم فرزها.