java - 对象链表的归并排序(升序)

Question

我正在做作业，经过几天的努力，我无法弄清楚为什么在实现归并排序后，我的列表仅包含链接列表中的最后一个对象。它不输出我的整个链表，只输出最后一个对象。如何更改代码以阻止列表在一个对象之后变为 null。

请注意:虽然我称它们为立方体，但我知道它们不是立方体，因为它们具有随机的长度、宽度和高度。分配指定它们被称为立方体，但具有这些随机数据字段。请忽略这一点。

public class SortingCubes {
    public static void main(String[] args) {
        System.out.println(" ");
        System.out.println("-----MY LINKED LIST-----");
        Cube headCubeLL = new Cube();                           //Create head cube
        int LLnum = 5;                                          //Change number of linked list items desired here
        for(int i = 0; i < LLnum; i++) {
            headCubeLL.length = Math.random() * 99 + 1;         //Create random L,W,H for each cube (between 1-100)
            headCubeLL.width = Math.random() * 99 + 1;
            headCubeLL.height = Math.random() * 99 + 1;
            headCubeLL.next = null;                             //Sets end of list to null
            if(headCubeLL.next == null) {                       //creates new cube until desired number is reached in the for loop
                Cube curr = new Cube(headCubeLL.length, headCubeLL.width, headCubeLL.height);
                headCubeLL = curr;
            }
            headCubeLL.next = null;                             //Sets last cube (next) to null to end the list.
            System.out.println(headCubeLL.toString() + " ");    //Print my Linked list until end
        }
        System.out.println(" ");
        System.out.println("-----NEW LINKED LIST AFTER MERGE SORT METHOD IS IMPLEMENTED (Asending Order by Volume)-----");
        long startTimeMergeSort = System.nanoTime();
        mergeSort(headCubeLL);
        long timeElapsedMergeSort = (System.nanoTime()- startTimeMergeSort);
        printList(headCubeLL);  //Method to print linked list
                System.out.println("Objects in list " + count(headCubeLL));
        long startTimeInsertionSort = System.nanoTime();

        System.out.println(" ");
        System.out.println("Time Record: ");
        System.out.println("Time elapsed for Merge sort on a Linked List: " + timeElapsedMergeSort + " Nanos");


    }       //End of Main

    public static void printList(Cube headCubeLL){
        while(headCubeLL != null){
            System.out.println(headCubeLL.toString() + " ");
            headCubeLL = headCubeLL.next;
        }
        System.out.println();
    }

    public static int count(Cube head){
        int count = 0;
        while(head != null){
            //System.out.println(head);
            count++;
            head = head.next;
        }
        return count;
    }

    public static Cube mergeSort(Cube headCubeLL) {

        if(headCubeLL == null || headCubeLL.next == null) {     //checking list is null
            return headCubeLL;
        }
        int count = 0;                  //To count the total number of elements
        Cube temp = headCubeLL;         //Temporary head of list 
        while(temp != null) {           //break up the list into two parts
            count++;                    //while not empty, count one and move temp to temp.next to evaluate
            temp = temp.next;
        }
        int middle = count/2;           //create an integer called middle and divide the length of your list (count) by 2
        Cube a = headCubeLL;            //another temp head cube for 1st split list
        Cube b = null;                  //another cube that is null
        Cube temp2 = headCubeLL;        //create another temp head cube for 2nd list    

        int countHalf = 0;              //start at half 0 again

        while(temp2 != null) {          //while temp I have for 2nd list is not null.... 
            countHalf++;                    //add count to get length of linked list
            Cube theNext = temp2.next;      //Create new cube that will be assigned to cube after head
            if(countHalf == middle) {       //once it reaches middle number
                temp2.next = null;          //end list (set head.next to null for list 2) 
                b = theNext;                //Take my empty null cube and assign it to end with null. 
            }
            temp2 = theNext;                //Otherwise - move along and my temp head will be the temp head.next
        }
        //Now I have 2 parts, List a and List b. 
        Cube half1 = mergeSort(a);          //Recursively call to sort each half
        Cube half2 = mergeSort(b);

        //Merge together
        Cube merged = merge(half1, half2);  //Call 2nd method to merge the 2 halves together
        //System.out.println(merged.toString());     //Print the L,W,H and Volume of each cube in my array

        return merged;      //return merged list. 
    }

    public static Cube merge(Cube a, Cube b) {      //parameters are the 2 half's of the original list
        Cube pt1 = a;                   //2 parts that I am going to merge as ascending lists according to volume
        Cube pt2 = b;

        Cube tempHead = new Cube();         //Temp head of my New list that cubes will be merged into
        Cube ptNew = tempHead;              //Temp Head for List my new list

        while(pt1 != null || pt2 != null) {     //While either list is not empty
            if(pt1 == null) {                   //but if first is null  
                ptNew.next = new Cube(pt2.cubeVolume());    //create new cube for every cube volume
                pt2 = pt2.next;                 //loop
            }
            else if(pt2 ==null){                //but if 2nd is null
                ptNew.next = new Cube(pt1.cubeVolume());    //create new cube for every cube volume
                pt1 = pt1.next;                 //loop
                ptNew = ptNew.next;             //move on by assigning moving to next cube creating when pt2 is == null
            }
            else {
                if(pt1.cubeVolume() < pt2.cubeVolume()) {       //moving while merging - comparing volumes of the head of each list
                    ptNew.next = new Cube(pt1.cubeVolume());    //When one is greater then new cube creating in new list and cube is placed accordingly
                    pt1 = pt1.next;         //loop
                    ptNew = ptNew.next;     //loop through new merged list for next comparison
                }
                else if(pt1.cubeVolume() == pt2.cubeVolume()) { //statement if the cubes volumes are equal
                    ptNew.next = new Cube(pt1.cubeVolume());
                    ptNew.next.next = new Cube(pt1.cubeVolume());
                    ptNew = ptNew.next.next;
                    pt1 = pt1.next;             //place one next to the other
                    pt2 = pt2.next;
                }
                else {
                    ptNew.next = new Cube(pt2.cubeVolume());        //else made new cube in new list and place pt2 head
                    pt2 = pt2.next;             //loop  
                    ptNew = ptNew.next;             //loop
                }

            }
        }
        return tempHead.next;           //return new merged list
    }

}   //End of Class

我的Cube类:(全部正确仅供引用)

public class Cube {

    double length;
    double width;
    double height;
    Cube next = null;

    public Cube() { //Default Constructor
    }
    public Cube(double volume) {
        volume = this.cubeVolume();
    }

    public Cube(Double length, double width, double height) {
        this.length = length;
        this.width = width;
        this.height = height;
        this.next = next;
    }

    public String toString() {      //Print into a String
        return "CUBE Volume: (" + cubeVolume() + ") ----- CUBE Length: ("+ this.length +") ----- CUBE Width (" + this.width + ") ----- CUBE Height (" + this.height + ")";
    }
    //Set length
    public void setLength(double length) {
        this.length = length;
    }

    //Get length
    public double getLength() {
        return this.length;
    }

    //Set Width
    public void setWidth(double width) {
        this.width = width; 
    }

    //Get Width
    public double getWidth() {
        return this.width;
    }

    //Set Height
    public void setheight(double height) {
        this.height = height;
    }

    //Set Height
    public double setHeight() {
        return this.height;
    }

    //Set Next
    public void setNext(Cube next) {
        this.next = next;
    }

    //Get Next
    public Cube getNext() {
        return this.next;
    }

    public double cubeVolume () {
        double volume = (length*width*height);
        //System.out.println("TEST: " + volume);
        return volume;
    }

}       //End of Class

输出

-----MY LINKED LIST-----
CUBE Volume: (14550.645379921463) ----- CUBE Length: (19.526751823368887) ----- CUBE Width (54.77537177724803) ----- CUBE Height (13.604009167732666) 
CUBE Volume: (1631.5144309742377) ----- CUBE Length: (40.72878317573845) ----- CUBE Width (22.07526604887876) ----- CUBE Height (1.8146109949933575) 
CUBE Volume: (17837.576670179817) ----- CUBE Length: (4.606784797762423) ----- CUBE Width (78.5447210731351) ----- CUBE Height (49.29704940251802) 
CUBE Volume: (113668.01972101796) ----- CUBE Length: (24.366242383656253) ----- CUBE Width (54.33809524521938) ----- CUBE Height (85.85099307890556) 
CUBE Volume: (432771.5800393206) ----- CUBE Length: (83.95704403819472) ----- CUBE Width (56.0616051224998) ----- CUBE Height (91.94668276748753) 

-----NEW LINKED LIST AFTER MERGE SORT METHOD IS IMPLEMENTED (Asending Order by Volume)-----
CUBE Volume: (432771.5800393206) ----- CUBE Length: (83.95704403819472) ----- CUBE Width (56.0616051224998) ----- CUBE Height (91.94668276748753) 

Objects in list 1

Time Record: 
Time elapsed for Merge sort on a Linked List: 11831 Nanos

Answer 1

问题出在您的 main 方法中，而不是您的排序方法中。这个区 block

        headCubeLL.next = null;                             //Sets end of list to null
        if(headCubeLL.next == null) {                       //creates new cube until desired number is reached in the for loop
            Cube curr = new Cube(headCubeLL.length, headCubeLL.width, headCubeLL.height);
            headCubeLL = curr;
        }
        headCubeLL.next = null;   

将始终进入if部分。您根本没有设置 curr 的 next 字段。因此，当您将 curr 分配给 headCubeLL 时，您会丢失 headCubeLL 之前的值。这意味着您的列表中永远只有一个对象。每次创建新对象时，您都会丢弃该对象。

你需要

• 删除最后的headCubeLL.next = null;
• 在创建对象 curr 后添加新行 curr.setNext(headCubeLL);。

这样，前面的 headCubeLL 将被记住，作为您刚刚创建的新对象的 next 元素。