剑指Offer 35 36

这是我参与8月更文挑战的第17天，活动详情查看：8月更文挑战

剑指 Offer 35. 复杂链表的复制

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
复制代码

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
复制代码

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
复制代码

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
复制代码

提示：

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

方法一

哈希表：对于原链表中的每个结点都在哈希表中存下一个对应的一模一样的结点；

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;
​
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node p = head;
        while(p != null) {
            map.put(p, new Node(p.val));
            p = p.next;
        }
        p = head;
        while(p != null) {
            map.get(p).next = map.get(p.next);
            map.get(p).random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}
复制代码

时间复杂度： O(n)

空间复杂度： O(1)

剑指 Offer 36. 二叉搜索树与双向链表

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

方法一

Morris原地遍历：

• 开两个指针，cur表示当前结点位置，pre表示前驱结点位置

• 如果cur不空

  • 如果cur没有左孩子，做操作（此题改变指针指向），pre指向cur，cur指向右孩子（第一次遍历到cur时，右孩子不会为空，要么为存在的右孩子，要么为cur的后继结点）

  • 如果有左孩子,在左孩子的子树中找到最右边的结点（即cur的前驱）或者等于cur自己（说明以cur为根的子树全部遍历完成）,

    • 如果前驱的右孩子为空，则指向cur
    • 不为空，则做操作，pre指向cur，cur指向右孩子

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
​
    public Node() {}
​
    public Node(int _val) {
        val = _val;
    }
​
    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        Node pre = null, p = root, head = null;
​
        while(p != null) {
            if (p.left != null) {//将cur的前驱的right指向自己
                Node tmp = p.left;
                while(tmp.right != null && tmp.right != p) tmp = tmp.right;
                if (tmp.right == null) {
                    tmp.right = p; //指向自己
                    p = p.left;
                }else {
                    p.left = pre;
                    pre = p;
                    p = p.right;
                }
            }else {
                if (pre == null) head = p;
                else pre.right = p;
                p.left = pre;
                pre = p;
                p = p.right;
            }
        }
        
        //首尾相接
        pre.right = head;
        head.left = pre;
        return head;
    }
}
复制代码

时间复杂度： O(n)

空间复杂度： O(1)

方法二

递归（中序）：中序遍历即是二叉搜索树的顺序，维护一个前驱结点pre，每次遍历到非空结点，和pre建立指针关系

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
​
    public Node() {}
​
    public Node(int _val) {
        val = _val;
    }
​
    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node root) {
        if (root == null) return;
        dfs(root.left);
        if (pre == null) head = root;
        else pre.right = root;
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}
复制代码

时间复杂度： O(n)

空间复杂度： O(n)