每日一题之《剑指offer》25,26题
第二十五题：复杂链表的复制
难易度：⭐⭐⭐
题目描述：
给定RandomListNode类
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
输入一个复杂链表
每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点
返回结果为复制后复杂链表的head
本题最简单的思路是使用HashMap
hash-key存储原链表的节点，hash-value则对应存储复制的节点。通过key-value的对应关系，可以推断:
node'.next = map.get(node.next);
以及
node'.rand = map.get(node.rand);
代码如下：
import java.util.HashMap;
public class Solution {
public RandomListNode Clone(RandomListNode pHead){
HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
RandomListNode cur = pHead;
while(cur != null){
map.put(cur,new RandomListNode(cur.label));
cur = cur.next;
}
cur = pHead;
while(cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(pHead);
}
}
能否不使用任何数据结构，就完成克隆整个链表呢？
思路二：
现有带有rand指针的链表如下,橙色为random,蓝色为next：
image.png
先不考虑rand指针，我们将链表复制成如下结构,红色node为复制的部分：
image.png
当形成这种结构的链表时，其实也就等同于hash表了。不难看出,复制的节点的next指针与rand指针应该如何指向，代码如下：
public class Solution {
public RandomListNode Clone(RandomListNode pHead){
if(pHead == null){
return null;
}
RandomListNode cur = pHead;
RandomListNode next = null;
while(cur != null){
next = cur.next;
RandomListNode curCopy = new RandomListNode(cur.label);
curCopy.next = next;
cur.next = curCopy;
cur = next;
}
cur = pHead;
while(cur != null){
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
cur = pHead;
RandomListNode returnNode = cur.next;
next = null;
while(cur != null){
next = cur.next;
cur.next = next.next;
cur = cur.next;
next.next = cur == null ? null : cur.next;
}
return returnNode;
}
}
第二十六题：二叉搜索树与双向链表
难易度：⭐⭐⭐
已知 TreeNode类
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
要求不能创建任何新的结点，只能调整树中结点指针的指向。
例如：
对于这样一个二分搜索树来说 如果转换成一个有序的双向链表则为：
9 ⇌ 10⇌ 11⇌ 13⇌ 17⇌ 21⇌ 24
right等同于next，left等同于 last
对于本题思路其实可以转换为递归的思路：
对于一个节点来说，如果这个节点没有左子树和右子树，那么则返回自己
对于一个节点来说，如果这个节点有左子树，没有右子树，那么只需要将左子树转换为有序的双向链表，然后再让双向链表的最后一个节点的right指向node,让node的left指向左子树转换为双向链表的最后一个节点即可，然后返回
对于一个节点来说，如果这个节点有右子树，没有左子树...
对于一个节点来说，如果这个节点既有左子树，也有右子树...
本题只要将各种case全部罗列出来，然后将复杂的问题转换为简单问题，把细节忽略，从宏观角度看问题，就会迎刃而解：
代码如下：
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
if(pRootOfTree.left == null && pRootOfTree.right == null){
return pRootOfTree;
}
if(pRootOfTree.left != null && pRootOfTree.right == null){
return onlyLeftTree(pRootOfTree);
}else if(pRootOfTree.right != null && pRootOfTree.left == null){
return onlyRightTree(pRootOfTree);
}else{
return bothTree(pRootOfTree);
}
}
public TreeNode onlyLeftTree(TreeNode node){
TreeNode leftNode = Convert(node.left);
TreeNode cur = leftNode;
while(cur != null){
if(cur.right == null){
break;
}
cur = cur.right;
}
cur.right = node;
node.left = cur;
return leftNode;
}
public TreeNode onlyRightTree(TreeNode node){
TreeNode rightNode = Convert(node.right);
node.right = rightNode;
rightNode.left = node;
return node;
}
public TreeNode bothTree(TreeNode node){
TreeNode leftNode = Convert(node.left);
TreeNode cur = leftNode;
while(cur != null){
if(cur.right == null){
break;
}
cur = cur.right;
}
cur.right = node;
node.left = cur;
TreeNode rightNode = Convert(node.right);
node.right = rightNode;
rightNode.left = node;
return leftNode;
}
}
