2021.02.17 复杂链表的复制

今日题目：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
image.png
image.png
image.png
提示：

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

  • 节点数目不超过 1000 。

  • 思路：

    • 法一：用哈希表辅助，采用空间换时间，哈希表为Map，作为key的Node是原来链表中的结点，而作为值的Node是新建链表中对应的结点。分成两步走，第一步先建立起新的链表，此时把各结点的对应情况保存至map中，新链表各结点的random值都为null，第二步再从头开始遍历，利用哈希表处理random值即可。时间复杂度是O(n)，空间复杂度为O(n)。
    • 法二：第一步，先遍历一遍原链表，在原链表中的每个结点后边都新建一个结点，例如N后边拼接N`；第二步处理每个新结点的random值，它等于原结点random值的下一个；第三步，拆分两个单链表。

  • 自己的菜鸡代码：

    1. /*
    2. // Definition for a Node.
    3. class Node {
    4.   int val;
    5.   Node next;
    6.   Node random;
    8.   public Node(int val) {
    9.       this.val = val;
    10.       this.next = null;
    11.       this.random = null;
    12.   }
    13. }
    14. */
    15. class Solution {
    16.   public Node copyRandomList(Node head) {
    17.       Map<Node,Node> map = new HashMap<>();
    18.       Node p = head, newHead = null, q = null;
    19.       while(p != null){
    20.           Node node = new Node(p.val);
    21.           map.put(p, node);
    22.           if(p == head) newHead = node;
    23.           else q.next = node;
    24.           q = node;
    25.           p = p.next;
    26.       }
    28.       p = head;
    29.       q = newHead;
    30.       while(p != null){
    31.           q.random = map.get(p.random);
    32.           p = p.next;
    33.           q = q.next;
    34.       }
    35.       return newHead;
    36.   }
    37. }

  • 运行结果：

法一（左）、法二（右）
image.pngimage.png

2021.02.17 二叉搜索树与双向链表

今日题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
image.png
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
image.png
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

  • 思路：
    • 法一：（自己写的）递归中序遍历二叉树，用一个辅助的哈希表保存中序遍历序列，最后遍历一遍哈希表，修改各个结点的指针，这样子时间复杂度和空间复杂度都很高。
    • 法二：（大佬的）在中序递归遍历时，就进行指针的处理。若root==null，返回，否则先递归遍历左子树，设置两个全局变量，一个是pre用于指向前一个结点，当pre == null时，当前结点就是第一个结点，令另一个全局变量head指向该结点，当pre ！= null时，令当前结点的左指针指向pre，令pre的右指针指向当前结点，再让pre = 当前结点（当前结点是下一个结点的前结点），再递归遍历右子树。最后pre指向的是最后一个结点，令head的左指针指向pre，pre的右指针指向head，返回head即可。时间复杂度为O(n)，空间复杂度为O(n)。

  • 自己的菜鸡代码： ```java /* // Definition for a Node. class Node { public int val; public Node left; public Node right;

    public Node() {}

    public Node(int _val) {

    1.   val = _val;

    }

    public Node(int _val,Node _left,Node _right) {

    1.   val = _val;
    2.   left = _left;
    3.   right = _right;

    } }; */ class Solution { private LinkedList list = new LinkedList<>(); public Node treeToDoublyList(Node root) {

    1.   // 按中序遍历序列的顺序线索化 
    2.   // 试一下用空间换时间
    3.   if(root == null) return root;
    4.   InOrder(root);
    5.   Node pre = list.getLast();
    6.   Node head = list.getFirst();
    7.   while(!list.isEmpty()){
    8.       Node node = list.removeFirst();
    9.       node.left = pre;
    10.       if(!list.isEmpty()){
    11.           node.right = list.getFirst();
    12.       }else{
    13.           node.right = head;
    14.       }
    15.       pre = node;
    16.   }
    17.   return head;

    }

    void InOrder(Node root){

    1.   if(root == null) return;
    2.   if(root.left != null){
    3.       InOrder(root.left);
    4.   }
    5.   list.add(root);
    6.   if(root.right != null){
    7.       InOrder(root.right);
    8.   }

    } }

// 法二 /* // Definition for a Node. class Node { public int val; public Node left; public Node right;

  1. public Node() {}
  3. public Node(int _val) {
  4.     val = _val;
  5. }
  7. public Node(int _val,Node _left,Node _right) {
  8.     val = _val;
  9.     left = _left;
  10.     right = _right;
  11. }

}; */ class Solution { private Node pre, head; public Node treeToDoublyList(Node root) { if(root == null) return null; pre = null; dfs(root); head.left = pre; pre.right = head; return head; }

  1. void dfs(Node root){
  2.     if(root == null) return;
  3.     dfs(root.left);
  4.     root.left = pre;
  5.     if(pre != null){
  6.         pre.right = root;
  7.     }else{
  8.         head = root;
  9.     }
  10.     pre = root;
  11.     dfs(root.right); 
  12. }

} ```

  • 运行结果：

法一（左）、法二（右）：
image.pngimage.png