add q138

yuanguangxin · yuanguangxin · commit d4dc36a4c942 · 2020-02-28T22:43:23.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/README.md b/README.md
@@ -10,6 +10,7 @@
 
 * [q2_两数相加](/src/链表操作/q2_两数相加)
 * [q206_反转链表](/src/链表操作/q206_反转链表)
+* [q138_复制带随机指针的链表](/src/链表操作/q138_复制带随机指针的链表)
 
 ### 双指针遍历/滑动窗口
 
diff --git a/src/链表操作/q138_复制带随机指针的链表/f1/Node.java b/src/链表操作/q138_复制带随机指针的链表/f1/Node.java
@@ -0,0 +1,13 @@
+package 链表操作.q138_复制带随机指针的链表.f1;
+
+class Node {
+    int val;
+    Node next;
+    Node random;
+
+    public Node(int val) {
+        this.val = val;
+        this.next = null;
+        this.random = null;
+    }
+}
diff --git a/src/链表操作/q138_复制带随机指针的链表/f1/Solution.java b/src/链表操作/q138_复制带随机指针的链表/f1/Solution.java
@@ -0,0 +1,29 @@
+package 链表操作.q138_复制带随机指针的链表.f1;
+
+import java.util.HashMap;
+
+/**
+ * 用Map存储遍历过的节点，时间o(n)，额外空间o(n)
+ */
+public class Solution {
+
+    HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();
+
+    public Node copyRandomList(Node head) {
+
+        if (head == null) {
+            return null;
+        }
+        if (this.visitedHash.containsKey(head)) {
+            return this.visitedHash.get(head);
+        }
+
+        Node node = new Node(head.val);
+
+        this.visitedHash.put(head, node);
+        node.next = this.copyRandomList(head.next);
+        node.random = this.copyRandomList(head.random);
+
+        return node;
+    }
+}
diff --git a/src/链表操作/q138_复制带随机指针的链表/f2/Node.java b/src/链表操作/q138_复制带随机指针的链表/f2/Node.java
@@ -0,0 +1,13 @@
+package 链表操作.q138_复制带随机指针的链表.f2;
+
+class Node {
+    int val;
+    Node next;
+    Node random;
+
+    public Node(int val) {
+        this.val = val;
+        this.next = null;
+        this.random = null;
+    }
+}
diff --git a/src/链表操作/q138_复制带随机指针的链表/f2/Solution.java b/src/链表操作/q138_复制带随机指针的链表/f2/Solution.java
@@ -0,0 +1,39 @@
+package 链表操作.q138_复制带随机指针的链表.f2;
+
+/**
+ * 在每一个链表的节点后都新连一个节点之后操作 时间o(n) 额外空间o(1)
+ */
+public class Solution {
+    public Node copyRandomList(Node head) {
+
+        if (head == null) {
+            return null;
+        }
+
+        Node ptr = head;
+        while (ptr != null) {
+            Node newNode = new Node(ptr.val);
+            newNode.next = ptr.next;
+            ptr.next = newNode;
+            ptr = newNode.next;
+        }
+
+        ptr = head;
+
+        while (ptr != null) {
+            ptr.next.random = (ptr.random != null) ? ptr.random.next : null;
+            ptr = ptr.next.next;
+        }
+
+        Node ptrOldList = head;
+        Node ptrNewList = head.next;
+        Node headOld = head.next;
+        while (ptrOldList != null) {
+            ptrOldList.next = ptrOldList.next.next;
+            ptrNewList.next = (ptrNewList.next != null) ? ptrNewList.next.next : null;
+            ptrOldList = ptrOldList.next;
+            ptrNewList = ptrNewList.next;
+        }
+        return headOld;
+    }
+}
