查找链表的排列

Question

我有一个链表，我正在尝试生成它的所有排列。

链接列表由ListNode对象组成，这些对象仅包含一个整数和对下一个ListNode的引用。

我正试着做这样的事情：

public void generatePermutatoins(ListNode head) {
      //code that generates permutations
      //let's say it finds a permutation and stores the entire list in
      //ListNode singlePermutation;
      //printList(singlePermutation);
}

我想知道是否也有递归解决方案？不过，我对任何解决方案都很执着。

Answer 1

是的，如果你正确定义了你的问题，你可以很容易地递归地完成它
您有一个链接列表和对该列表的head的引用。您有一个函数，它递归地创建头之后所有元素的所有排列
当你得到结果时，你遍历每个排列，并在每个位置添加head，生成最后一个排列
如果你还没有弄清楚，这就是你的递归函数。下面是Java中的骨架/伪代码，让您开始学习。addEachPosition(permutation, node.value);将列表中所有可能位置的值相加

public List<List<Integer>> getPermutations(ListNode currentNode) {  
       if(currentNode == null) {  
             return new ArrayList<ListNode>();  
       }   
       List<List<Integer>> nextPermutations = getPermutations(currentNode.next);  
       addToPermutations(currentNode, nextPermutations);  
       return nextPermutations;  
}  
public void addToPermutations(ListNode node, List<List<Integer>> permutations) {  
   for(List<Integer> permutation:permutations) {  
      addEachPosition(permutation, node.value);        
   }  
}  

Answer 2

这种非递归（迭代）实现可能会有所帮助：Collections.permutations.