复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路
从左到右遍历链表，将每个节点复制成相应的副本放入哈希表中，再 从左到右遍历链表，完成副本的next和random指针。返回头节点。
代码
import java.util.HashMap;
/**
* 剑指offer一刷：复杂链表的复制
*
* @author User
* @create 2019-05-22-18:13
*/
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
public class jzo25 {
public RandomListNode Clone(RandomListNode pHead) {
HashMap<RandomListNode,RandomListNode> map=new HashMap<>();
RandomListNode currentNode=pHead;
//将链表结点复制到哈希表map中
while (currentNode!=null){
map.put(currentNode,new RandomListNode(currentNode.label));
currentNode=currentNode.next;
}
currentNode=pHead;
//完成哈希表中节点的next和random指针的设置
while (currentNode!=null){
map.get(currentNode).next=map.get(currentNode.next);
map.get(currentNode).random=map.get(currentNode.random);
currentNode=currentNode.next;
}
return map.get(pHead);
}
public static void main(String[] args){
RandomListNode node1=new RandomListNode(1);
RandomListNode node2=new RandomListNode(2);
RandomListNode node3=new RandomListNode(3);
RandomListNode node4=new RandomListNode(4);
node1.next=node2;
node1.random=node3;
node2.next=node3;
node2.random=node4;
node3.next=node4;
node3.random=null;
node4.next=null;
node4.random=node1;
jzo25 so=new jzo25();
System.out.println(so.Clone(node1).label);
}
}
二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路
利用queue或者stack，按照二叉树中序遍历，将每个节点放入；按照弹出顺序连接所有节点
代码
BINBIN:
package offer.bin.first;
import java.util.Stack;
/**
* 剑指offer一刷：二叉搜索树与双向链表
*
* @author User
* @create 2019-05-22-19:02
*/
public class jzo26 {
// public TreeNode Convert(TreeNode pRootOfTree) {
// Queue<TreeNode> queue=new LinkedList<>();
// if (queue.isEmpty()){
// return pRootOfTree;
// }
// pRootOfTree=queue.poll();
// TreeNode pre=pRootOfTree;
// pre.left=null;
// TreeNode currentNode=null;
// //完成双向链表的转换
// while (!queue.isEmpty()){
// currentNode=queue.poll();
// pre.right=currentNode;
// currentNode.left=pre;
// pre=currentNode;
// }
// pre.right=null;
// return pRootOfTree;
// }
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree==null){
return null;
}
Stack<TreeNode> stack=new Stack<>();
TreeNode p=pRootOfTree;
TreeNode pre=null; //pre是中序遍历的上一节点
boolean isFirst=true;
while (p!=null||!stack.isEmpty()){
while (p!=null){
stack.push(p);
p=p.left;
}
p=stack.pop();
if (isFirst){
pRootOfTree=p; //将中序便利第一个结点
pre=pRootOfTree;
isFirst=false;
}else {
pre.right=p;
p.left=pre;
pre=p;
}
p=p.right;
}
return pRootOfTree;
}
public static void main(String[] args){
TreeNode node1=new TreeNode(1);
TreeNode node2=new TreeNode(2);
TreeNode node3=new TreeNode(3);
TreeNode node4=new TreeNode(4);
TreeNode node5=new TreeNode(5);
TreeNode node6=new TreeNode(6);
TreeNode node7=new TreeNode(7);
TreeNode node8=new TreeNode(8);
TreeNode node9=new TreeNode(9);
node6.left=node4;
node4.left=node2;
node4.right=node5;
node2.left=node1;
node2.right=node3;
