java - Java 打乱链表

Question

我很难使用伪代码进行洗牌算法并将其转换为有效的 java 代码。我正在尝试打乱链接列表。总的来说，该方法获取链表头部的指针，并随机返回指向同一链表头部的指针。我想使用我创建的 getLength 和 getItem 方法。

public static ListElement shuffle(ListElement head){
  head = head.getLength();
  ListElement head2= null;
  while( head == null) {
    int random = (int) Math.random() *  n;
    for(int i=0;i<random;i++){
        head= head.getNext();
    }
  }
  return head;    
}

伪代码:

A list L of length n
A new list R, empty
while L is not empty
   pick a random k 
   such that 0<=k<= (length L)
   remove the kth element of L
      call it e
   prepend e to R

Answer 1

我只是稍微重写了代码，使其遵循伪代码。

ListElement head2 = null;
int length = head.getLength();

while (head != null) {
    int k = (int) Math.random() * length;

    // Assume there is function deleteAt(index) that removes
    // the element at specified index and returns the deleted
    // element
    ListElement e = head.deleteAt(k);
    // Although I can just give the implementation - I'll leave this
    // as exercise.

    // You can have a function that add element to front
    // head2.addFront(e);
    e.setNext(head2);
    head2 = e;

    // Instead of querying the length again
    // decrement the length
    length--;
}
return head;