LeetCode剑指offer——复杂链表的复制、二叉搜索树与双向链表

复杂链表的复制

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

提示：

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

代码：

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        p = head
        Hash = {None:None}
        while p:
            Hash[p] = Node(p.val)
            p = p.next
        p = head
        while p:
            Hash[p].next = Hash[p.next]
            Hash[p].random = Hash[p.random]
            p = p.next
        return Hash[head]

本题用一个哈希表辅助存储链表，时间复杂度O(n)，空间复杂度O(n)。

二叉搜索树与双向链表

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

我们希望将这个二叉搜索树转化为双向循环链表。树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。第一个节点为最小的节点，按大小顺序依次向后。

代码：

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left) 
            if self.pre: 
                self.pre.right, cur.left = cur, self.pre
            else: 
                self.head = cur
            self.pre = cur 
            dfs(cur.right) 
        
        if not root: return
        self.pre = None
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

使用中序遍历和递归从小到大的访问每个节点，并修改其指针指向。

时间复杂度和空间复杂度都是O(n)。