我该如何混洗链接列表中的节点？

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()))); 
    }      
} 

你做的掉期越多，这个列表就越随机化。