java - 使用最多 log N 额外内存和 N log N 时间对单链表进行混洗

Question

我试图通过递归方式对链表进行洗牌，将其分成两个列表，然后合并它们以确保随机洗牌。

我面临的两个问题是:

1. 当我运行程序时，第 56 行有一个无限循环，我告诉程序对第一个列表进行洗牌。
2. 我无法弄清楚如何在列表 1 和列表 2 的长度不同的情况下添加虚拟变量以确保洗牌的随机性。

PS - 我通过互联网搜索发现两个列表的长度应该相同以确保随机性，但我不知道其背后的逻辑。另外，如果有比我正在尝试的更好的方法，请告诉我。

提前致谢!

public class LinkedListShuffle
{
    static public class LinkedList<E>       // static nested class
    {
        private int N = 0;
        private Node first = null;

        public class Node
        {
            E elem;
            Node next;
        }

        public boolean isEmpty()
        {    return N == 0;    }

        public void push (E elem)
        {
            Node oldfirst = first;
            first = new Node(); 
            first.elem = elem;
            first.next = oldfirst;
            N++; 
        }

        public E pop()
        {
            E elem = first.elem;
            first = first.next;
            N--;
            return elem;
        }

        public int size ()
        {    return N;    }

    }

    public static void shuffle(LinkedList l)
    {
        if (l.size() == 1) return;

        LinkedList.Node current = l.first;


        LinkedList l1 = new LinkedList();
        LinkedList l2 = new LinkedList();

        while (! l.isEmpty())
        {
            l1.push(l.pop());
            if (! l.isEmpty()) l2.push(l.pop());
        }
        shuffle(l1);
        shuffle(l2);

        /*------------------------------------------    
        * if (l2.size() < l1.size())
        * introduce a dummy node to ensure the
        * randomness in the process of shuffling
        -----------------------------------------*/

        merge(l, l1, l2);

        /*-----------------------------------------------
        * remove the dummy variable
        * ----------------------------------------------*/       
    }

    public static void merge (LinkedList l, LinkedList l1, LinkedList l2)
    {
        while (l1.size() != 0 && l2.size() != 0)
        {
            double chance = StdRandom.uniform(1);
            if (chance < 0.5) l.push(l1.pop());
            else              l.push(l2.pop());
        }

        if (! l1.isEmpty())
            while (! l1.isEmpty()) l.push(l1.pop());
        if (! l2.isEmpty())
            while (! l2.isEmpty()) l.push(l2.pop());
    }

    public static void main (String[] args)
    {
        LinkedList<String> l = new LinkedList<String>();
        LinkedList<String> copy = new LinkedList<String>();
        l.push("A"); l.push("B"); l.push("C"); l.push("D");
        l.push("E"); l.push("F"); l.push("G"); l.push("H");
        copy = l;

        while (copy.size() != 0) StdOut.println(copy.pop()+"  ");
        shuffle(l);
        while (l.size() != 0) StdOut.println(l.pop()+"  ");
    }
}

Answer 1

您的问题是，在调用 shuffle(l) 之前，在 main 方法中打印列表时，您清空了列表。

您正在将列表 l 分配给名为 copy 的变量，但该变量不包含列表的副本。它指的是同一个列表。当您调用copy.pop()时，您将从原始列表中删除一个元素。因此，您对空列表调用 shuffle。

public static void main (String[] args)
{
    LinkedList<String> l = new LinkedList<String>();
    LinkedList<String> copy = new LinkedList<String>();
    l.push("A"); l.push("B"); l.push("C"); l.push("D");
    l.push("E"); l.push("F"); l.push("G"); l.push("H");
    copy = l;

    while (copy.size() != 0) StdOut.println(copy.pop()+"  "); // remove this line
                                                              // and your method will
                                                              // work
    shuffle(l);
    while (l.size() != 0) StdOut.println(l.pop()+"  ");
}

当然，这意味着您的 shuffle 方法无法处理空列表作为输入。

这可以通过一个小修复来解决:

public static void shuffle(LinkedList l)
{
    if (l.size() <= 1) return; // instead of == 1
    ...