排序LinkedList沒有明顯的訪問節點？

Question

大家好。我希望有人能夠對此有所瞭解。我有一個要求我整理一個給定的LinkedList，並返回排序列表如下一門功課的問題：

private LinkedList<T> list; 

// constructor 
public SortedLinkedList(LinkedList<T> in){ 
}  

現在，我已經得到了我認爲（我可以用一個簡單的歸併）邏輯下，但我看不到自己訪問節點的方法。想到的東西也是quicksort的一個細微變化，也就是說，將頭部作爲關鍵點，並將鏈表分成兩個較小的，重複然後合併...但我想知道我是否可以用其他方式做到這一點。由於我們不能真正訪問任何私有節點，所以我沒有任何好的想法。

由於顯而易見的原因，我們不允許使用Collections或Arrays進行排序。我們只允許使用Java LinkedList和單個專用字段。

感謝您的任何意見。

編輯：我寧願避免使用toArray，如果我可以幫助它。

Answer 1

這是正常的，你不需要任何私人訪問。將列表作爲列表進行威脅 - 您已獲取並設置方法。

雖然很重要，但要考慮鏈表是隨機訪問緩慢的！所以你需要找到一種與彼此相鄰的節點工作的排序。

在這種情況下，類似冒泡排序實際上可能效果最好。 不起泡。 。該名稱是不同的，你需要cmp和交換neigbourh細胞。交換排序也許？

Answer 2

由於您不允許使用其他課程，我建議您使用冒泡排序。它的簡單性和性能並不差。以下是如何使用它：

public SortedLinkedList(LinkedList<T> in) { 
    bubbleSort(in); 
} 

private void bubbleSort(LinkedList<T> in) { 
    // Convert the LinkedList into an array called arr. You should know how to do this.. 
    // This code assumes that your resulting array is of type int. For others, adjust 
    // the code appropriately. 

    for(int i = arr.length - 1; i > 0; i--) { 
     for(int j = 0; j < i; j++) { 
      if(arr[j] > arr[j + 1]) 
       swap(array, j, j+1); 
     } 
    } 
} 

private void swap(int[] array, int i, int j) { 
    int temp = 0; 

    temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
}