25.复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
//一定注意考虑输入为空链表的情况
if(pHead == null) return null;
//第一步：克隆每个结点的值和next，并且将新节点放置在对应旧结点之后
RandomListNode node = pHead;
while(node != null){
RandomListNode cloneNode = new RandomListNode(node.label);
//cloneNode.label = node.label;
cloneNode.next = node.next;
node.next = cloneNode;
node = cloneNode.next;
}
//第二步：克隆每个随机指针
node = pHead;
while(node != null){
RandomListNode cloneNode = node.next;
if(node.random != null)
cloneNode.random = node.random.next;
node = cloneNode.next;
}
//第三步：拆分拼接的链表
node = pHead;
RandomListNode cloneHead = pHead.next;
while(node != null){
RandomListNode cloneNode = node.next;
node.next = cloneNode.next;
node = node.next;
if(node != null)
cloneNode.next = node.next;
else
cloneNode.next = null;
}
return cloneHead;
}
}
26.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) return null;
if(pRootOfTree.left == null && pRootOfTree.right == null) return pRootOfTree;
TreeNode left = Convert(pRootOfTree.left);
TreeNode node = left;
if(node == null)
pRootOfTree.left = null;
else{
while(node.right != null)
node = node.right;
pRootOfTree.left = node;
node.right = pRootOfTree;
}
TreeNode right = Convert(pRootOfTree.right);
pRootOfTree.right = right;
if(right != null)
right.left = pRootOfTree;
return left != null ? left : pRootOfTree;
}
}
27.字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Solution {
ArrayList<String> result = new ArrayList<String>();
public ArrayList<String> Permutation(String str) {
if(str == null) return null;
char[] charArray = str.toCharArray();
permutation(charArray,0);
Collections.sort(result);
return result;
}
public void permutation(char[] charArray,int beginIdx){
if(beginIdx >= charArray.length) return;
if(beginIdx == charArray.length-1){
result.add(String.valueOf(charArray));
}
HashSet<Character> charSet = new HashSet<>();
for(int i = beginIdx;i<charArray.length;i++){
if(i == beginIdx){
charSet.add(charArray[i]);
permutation(charArray,beginIdx+1);
}else if(i != beginIdx && !charSet.contains(charArray[i])){
char temp = charArray[beginIdx];
charArray[beginIdx] = charArray[i];
charArray[i] = temp;
permutation(charArray,beginIdx+1);
temp = charArray[beginIdx];
charArray[beginIdx] = charArray[i];
charArray[i] = temp;
}
}
}
}