ArrayIndexOutOfBoundsException異常，當一個LinkedList

Question

好了，所以我有一個任務，它是這樣的：

Assume you have as input a singly-linked list containing N items (an instance of a LinkedList class in Java). You should rearrange the items in the LinkedList uniformly at random. Your algorithm should consume a logarithmic (or constant) amount of extra memory and run in time proportional to NlogN in the worst case.

對於算法我去了歸併，當其合併以隨機的方式這樣做。我不知道該怎麼做，我不知道該怎麼辦甚至可以肯定我以正確的方式做到這一點。

代碼：

import java.util.LinkedList; 

public class Q02 { 

public static void main(String[] args) { 

    LinkedList<Integer> list = new LinkedList<>(); 
    list.add(1); 
    list.add(2); 
    list.add(3); 
    list.add(4); 
    list.add(5); 
    list.add(6); 
    list.add(7); 
    list.add(8); 
    list.add(9); 
    list.add(0); 
    System.out.println("Shuffled list: "+shuffle(list)); 
} 

public static LinkedList shuffle(LinkedList list){ 
    int node = 10; //just a random node 
    if(list.size()<=1){ 
     return list; 
    } 
    LinkedList<Integer>list1 = new LinkedList<>(); 
    LinkedList<Integer>list2 = new LinkedList<>(); 

    while(!list.isEmpty()){ 
     list1.add((Integer) list.removeFirst()); 
     if(!list.isEmpty()){ 
      list2.add((Integer) list.removeFirst()); 
     } 
    } 
    shuffle(list1); 
    shuffle(list2); 

    if(list2.size() < list1.size()){ 
     int i = (int)(Math.random() * list2.size()); 
     list2.set(i, node); 
    } 

    while(!list1.isEmpty()&&!list2.isEmpty()){ 
     int rand = (int)(Math.round(Math.random())); 
     if(rand == 1){ 
      list.add(list1.removeFirst()); 
     } 
     else if(rand == 0){ 
      list.add(list2.removeFirst()); 
     } 
    } 
    //If any of list1 or list2 are still empty add everything to list 
    if(!list1.isEmpty()){ 
     list.add(list2.clone()); 
    } 
    if(!list2.isEmpty()){ 
     list.add(list1.clone()); 
    } 
    list.remove(node); 
    return list; 
} 

} 

以下是錯誤：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 10, Size: 2 
at java.util.LinkedList.checkElementIndex(LinkedList.java:553) 
at java.util.LinkedList.remove(LinkedList.java:523) 
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:62) 
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:39) 
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:39) 
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:39) 
at kth.id2010.lab.lab03.Q02.Q02.main(Q02.java:22) 

Answer 1

如果你得到一個ArrayIndexOutOfBoundsException，這意味着某處您嘗試使用索引來訪問LinkedList項目那是無效的。例如，如果您的LinkedList具有10項目，則listOfSize10.set(10, node)將產生ArrayIndexOutOfBoundsException。

最有可能你所看到的錯誤從這些線路莖：

int i = (int)(Math.random() * list2.size()); 
list2.set(i, node); 

你能保證i總是大於或等於0和小於list2.size()？

更新 看到您的堆棧跟蹤後，它看起來像錯誤來自這些行：

int node = 10; //just a random node 
list.remove(node); 

在這裏，你顯然試圖在指數10刪除的項（或，第十項）當列表中只有10項目時。所以你的數組索引超出了界限。