# 剑指offer第四天

### 25.复杂链表的复制

/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
{
//一定注意考虑输入为空链表的情况
//第一步：克隆每个结点的值和next，并且将新节点放置在对应旧结点之后
while(node != null){
RandomListNode cloneNode = new RandomListNode(node.label);
//cloneNode.label = node.label;
cloneNode.next = node.next;
node.next = cloneNode;
node = cloneNode.next;
}
//第二步：克隆每个随机指针
while(node != null){
RandomListNode cloneNode = node.next;
if(node.random != null)
cloneNode.random = node.random.next;
node = cloneNode.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;
}
}
}

### 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.==字符串的排列==

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){
}
HashSet<Character> charSet = new HashSet<>();
for(int i = beginIdx;i<charArray.length;i++){
if(i == beginIdx){
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;
}
}
}
}

129 篇文章39 人订阅

0 条评论

## 相关文章

### Hashtable源码解析（JDK1.8）

1 package java.util; 2 3 import java.io.*; 4 import java.util.concu...

31140

### LeetCode 872. Leaf-Similar Trees

Consider all the leaves of a binary tree.  From left to right order, the values ...

15500

### XStream、JAXB 日期(Date)、数字(Number)格式化输出xml

XStream、Jaxb是java中用于对象xml序列化/反序列化 的经典开源项目，利用它们将对象转换成xml时，经常会遇到日期(Date)、数字按指定格式输出...

28270

27910

### Java源码阅读之TreeMap(红黑树) - JDK1.8

TreeMap实现了NavigableMap接口， 而NavigableMap则是通过sortedMap间接继承了Map接口，它定义了一系列导航方法，这些Map...

37630

12150

### 【Java入门提高篇】Day26 Java容器类详解（八）HashSet源码分析

前面花了好几篇的篇幅把HashMap里里外外说了个遍，大家可能对于源码分析篇已经讳莫如深了。

11740

13510

### LWC 62：742. Closest Leaf in a Binary Tree

LWC 62：742. Closest Leaf in a Binary Tree 传送门：742. Closest Leaf in a Binary Tree...

312100

15640