每日一题之《剑指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;
    }
}