java - 查找链表的排列

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

要求提供代码的问题必须表现出对所解决问题的最低限度的了解。包括尝试的解决方案、为什么它们不起作用以及预期结果。另请参阅:Stack Overflow question checklist

已关闭 9 年前。

Improve this 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 之后所有元素的所有排列。
当您获得结果时，您将检查每个排列，并在每个位置添加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);        
   }  
}