我該如何混洗鏈接列表中的節點？

Question

我剛剛爲我的Java2課程開始了一個項目，我已經完全停下來了。我無法得到 這個方法。特別是當賦值不允許我們使用java中的任何其他數據結構或shuffle方法時。

所以我有一個Deck.class，其中我已經創建了一個鏈表，其中包含52個節點，可容納52張卡片。

public class Deck { 

    private Node theDeck; 
    private int numCards; 

    public Deck() 
    { 
     while(numCards < 52) 
     { 
      theDeck = new Node (new Card(numCards), theDeck); 
      numCards++; 
     } 
    } 

    public void shuffleDeck() 
    {   
     int rNum; 
     int count = 0; 
     Node current = theDeck; 
     Card tCard; 
     int range = 0; 

     while(count != 51) 
     { 
      // Store whatever is inside the current node in a temp variable 
       tCard = current.getItem(); 

      // Generate a random number between 0 -51  
       rNum = (int)(Math.random()* 51); 

      // Send current on a loop a random amount of times 
       for (int i=0; i < rNum; i ++) 
       current = current.getNext(); ******<-- (Btw this is the line I'm getting my error, i sort of know why but idk how to stop it.) 

      // So wherever current landed get that item stored in that node and store it in the first on 
      theDeck.setItem(current.getItem()); 

      // Now make use of the temp variable at the beginning and store it where current landed 
      current.setItem(tCard); 

      // Send current back to the beginning of the deck 
      current = theDeck; 

      // I've created a counter for another loop i want to do  
      count++; 

      // Send current a "count" amount of times for a loop so that it doesn't shuffle the cards that have been already shuffled. 
      for(int i=0; i<count; i++) 
      current = current.getNext(); ****<-- Not to sure about this last loop because if i don't shuffle the cards that i've already shuffled it will not count as a legitimate shuffle? i think? ****Also this is where i sometimes get a nullpointerexception**** 

     } 

    } 

} 

現在，我得到的各種錯誤 時，我呼籲這個方法：

• 它有時會洗牌只是2張卡，但有時它會洗牌3 - 5張牌，然後給我一個空指針異常。 我已經指出，它給了我這個錯誤用星號在我上面的代碼

• 在一個點上我得到了它的洗牌13卡，但隨後每次它這樣做，它並沒有完全打亂他們的正確途徑。一張牌總是重複。

• 在另一點我得到了所有52張牌通過while循環，但它又一次重複一張牌。

所以我真的需要一些輸入我做錯了什麼。在我的代碼結束時，我認爲我的邏輯完全錯誤，但我似乎無法找出解決方法。

Answer 1

燮傢伙，所以我終於找到它了，這是我的洗牌方法

public void shuffleDeck() 
{   

    Node current; 
    Node random; 
    Card cTemp; 
    int rand; 

    rand = (int)(Math.random() * numCards); 

    for (int j=0; j<rand; j++) 
    { 
     for (int i=0; i<numCards; i++) 
     { 
      current = theDeck; 
      random = theDeck; 

      rand = (int)(Math.random() * numCards); 

      for(int k = 0; k < rand; k++) 
       random = random.getNext(); 

      cTemp = current.getItem(); 
      current.setItem(random.getItem()); 

      random.setItem(cTemp); 
     } 
    } 
} 

我的更新和它的作品^ _^ 感謝您的輸入壽。 =）

Answer 2

如果您被授權使用輔助數據結構，一種方法是簡單地計算剩餘卡片數量內的隨機數字，選擇該卡片，將其移動到二級結構的末尾直到空白，然後替換您的列表與輔助列表。

Answer 3

似乎很囉嗦。

我的東西去像下面這樣：

public void shuffleDeck() { 
    for(int i=0; i<52; i++) { 
     int card = (int) (Math.random() * (52-i)); 
     deck.addLast(deck.remove(card)); 
    } 
} 

所以每張卡只是被移動到甲板以隨機順序回來。

Answer 4

我實現洗牌使用分而治之算法

public class LinkedListShuffle 
{ 
    public static DataStructures.Linear.LinkedListNode<T> Shuffle<T>(DataStructures.Linear.LinkedListNode<T> firstNode) where T : IComparable<T> 
    { 
     if (firstNode == null) 
      throw new ArgumentNullException(); 

     if (firstNode.Next == null) 
      return firstNode; 

     var middle = GetMiddle(firstNode); 
     var rightNode = middle.Next; 
     middle.Next = null; 

     var mergedResult = ShuffledMerge(Shuffle(firstNode), Shuffle(rightNode)); 
     return mergedResult; 
    } 

    private static DataStructures.Linear.LinkedListNode<T> ShuffledMerge<T>(DataStructures.Linear.LinkedListNode<T> leftNode, DataStructures.Linear.LinkedListNode<T> rightNode) where T : IComparable<T> 
    { 
     var dummyHead = new DataStructures.Linear.LinkedListNode<T>(); 
     DataStructures.Linear.LinkedListNode<T> curNode = dummyHead; 

     var rnd = new Random((int)DateTime.Now.Ticks); 
     while (leftNode != null || rightNode != null) 
     { 
      var rndRes = rnd.Next(0, 2); 
      if (rndRes == 0) 
      { 
       if (leftNode != null) 
       { 
        curNode.Next = leftNode; 
        leftNode = leftNode.Next; 
       } 
       else 
       { 
        curNode.Next = rightNode; 
        rightNode = rightNode.Next; 
       } 
      } 
      else 
      { 
       if (rightNode != null) 
       { 
        curNode.Next = rightNode; 
        rightNode = rightNode.Next; 
       } 
       else 
       { 
        curNode.Next = leftNode; 
        leftNode = leftNode.Next; 
       } 
      } 

      curNode = curNode.Next;      
     } 
     return dummyHead.Next; 
    } 

    private static DataStructures.Linear.LinkedListNode<T> GetMiddle<T>(DataStructures.Linear.LinkedListNode<T> firstNode) where T : IComparable<T> 
    { 
     if (firstNode.Next == null) 
      return firstNode; 

     DataStructures.Linear.LinkedListNode<T> fast, slow; 
     fast = slow = firstNode; 
     while (fast.Next != null && fast.Next.Next != null) 
     { 
      slow = slow.Next; 
      fast = fast.Next.Next; 
     } 
     return slow; 
    } 
} 

Answer 5

過這個剛剛來到，並決定發佈一個更簡潔的解決方案，它允許你指定多少洗牌你想要做一個鏈表。

出於答案的目的，您有一個鏈接列表，其中包含PlayingCard對象;

LinkedList<PlayingCard> deck = new LinkedList<PlayingCard>(); 

而且洗牌他們使用這樣的東西;

public void shuffle(Integer swaps) {  
    for (int i=0; i < swaps; i++) { 
     deck.add(deck.remove((int)(Math.random() * deck.size()))); 
    }      
} 

你做的掉期越多，這個列表就越隨機化。