爲什麼不能在鏈接列表上合併排序？

Question

（免責聲明：對於學校，所以不能導入其他Java實用程序）

所以我必須在鏈表上合併排序，而且我幾乎把它全部關閉了。有

class musicNode { 
String track; // The name of the track 
int played= 0; // The number of times played 
int shuffleTag= 0; // For shuffling 
musicNode next; 

public musicNode() {  // Here's how we construct an empty list. 
    next = null; 
} 
public musicNode(String t) { 
    track = t; next = null; 
} 
public musicNode(String t, musicNode ptr) { 
    track = t; next = ptr; 
} 

public boolean LTTrack(musicNode x) { // Compares tracks according to alphabetical order on strings 
    if (this.track.compareTo(x.track)<=0) return true; 
    else return false; 
} 
}; 

// This class represents a playlist; 
// We assume that each track appears at most once in the playlist 

public class MusicPlayer { 
protected musicNode head = null; // Pointer to the top of the list. 
int length=0; // the number of nodes in the list. 
boolean debug= false; 

public MusicPlayer() { 
} 
public void setToNull() { 
    head = null; 
} 
public boolean isEmpty() { 
    return head == null; 
} 

public musicNode head() { 
    return head; 
} 

void insertTrack(String name) { // Inserts a new track at the top of the list. 
    musicNode temp= new musicNode(name, head); 
    head= temp; 
    length++; 
} 

void sortTrack() { // TODO 
    musicNode main = this.head; 
    mergeSort(main); 
} 


public musicNode mergeSort(musicNode head) { 
    if ((head == null) || (head.next == null)){ 
     return head; 
    } 
    musicNode left = head; 
    musicNode right = head.next; 

    while((right != null) && (right.next != null)){ 
     head = head.next; 
     right = (right.next).next; 
    } 
    right = head.next; 
    head.next = null; 

    return merge(mergeSort(left), mergeSort(right)); 
} 

也是這個JUnit測試：這是

public void testSortMixed() { 
    MusicPlayer trackList= new MusicPlayer(); 
    trackList.insertTrack("d"); 
    trackList.insertTrack("b"); 
    trackList.insertTrack("e"); 
    trackList.insertTrack("a"); 
    trackList.insertTrack("c"); 

    MusicPlayer trackListTwo= new MusicPlayer(); 
    trackListTwo.insertTrack("e"); 
    trackListTwo.insertTrack("d"); 
    trackListTwo.insertTrack("c"); 
    trackListTwo.insertTrack("b"); 
    trackListTwo.insertTrack("a"); 

    trackList.sortTrack(); 
    musicNode tmp= trackList.head; 
    musicNode tmp2= trackListTwo.head; 
    for(int i=0; i< 5; i++){ 
     assertEquals(tmp2.track, tmp.track); 
     tmp2= tmp2.next; 
     tmp=tmp.next; 
    } 
} 

的問題是，它根據你插入的最後一首曲目排序，只有從那時起。所以說你從a-f插入字母，但你插入的最後一個是「c」，它只會顯示你「cdef」。但是，如果最後一個是「一個」，那麼它按預期工作。

所以它是如何工作的，當你插入一個軌道它被插入到列表的開始，而不是結束，成爲頭部。我覺得這可能是什麼搞砸了，因爲我從我的筆記和在線上調整和查看哪些插入底部。

我不知道如何解釋這個。另外我知道它根據最後插入的內容進行排序（在上面的JUnit測試中，它排序爲「cde」，因爲我創建了一個主要函數並隨其播放）

任何幫助讚賞。

Answer 1

的關鍵點是在方法sortTrack下聯：

void sortTrack() { 
    musicNode main = this.head; 
    this.head = mergeSort(main); // you forgot to set the head of linked list to the merged 
} 

我已經在我的筆記本電腦進行了測試，萬事如意現在沒事的xD