复制带随机指针的链表

yingl · yingl · commit e192c6c43569 · 2016-07-30T11:44:10.000+08:00
diff --git a/copy_list_with_random_pointer.py b/copy_list_with_random_pointer.py
@@ -0,0 +1,41 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param head: A RandomListNode
+    # @return: A RandomListNode
+    def copyRandomList(self, head):
+        # write your code here
+        '''
+        &#24605;&#36335;&#22914;&#19979;&#65292;abcd...&#20195;&#34920;&#21407;&#38142;&#34920;&#65292;a'b'c'd'...&#20195;&#34920;&#26032;&#38142;&#34920;&#12290;()&#20869;&#20195;&#34920;random&#65292;'/'&#20195;&#34920;None&#12290;
+        &#21021;&#22987;&#29366;&#24577;&#65306;a(d)->b(/)->c(e)->d(a)
+        1. &#25554;&#20837;&#24182;&#22797;&#21046;&#21407;&#26469;&#30340;random&#33410;&#28857;&#65306;a(d)->a'(d)->b(/)->b'(/)->c(e)->c'(e)->d(a)->d'(a)
+        2. &#26356;&#26032;&#26032;&#33410;&#28857;&#30340;random&#65288;&#22240;&#20026;x&#25351;&#21521;x'&#65289;&#65306;a(d)->a'(d')->b(/)->b'(/)->c(e)->c'(e')->d(a)->d'(a')
+        3. &#25286;&#25104;&#20004;&#26465;&#38142;&#34920;&#24182;&#36820;&#22238;
+        '''
+        if not head:
+            return None
+        node = head
+        while node:
+            new_node = RandomListNode(node.label)
+            new_node.next, new_node.random = node.next, node.random
+            node.next = new_node
+            node = new_node.next
+        node = head.next
+        while node:
+            node.random = node.random.next
+            node = node.next  # &#21521;&#21069;&#20004;&#27493;
+            node = node.next
+        new_head, new_tail = None, None
+        node = head
+        while node:
+            prev = node
+            node = node.next
+            prev.next = node.next # prev.next&#20445;&#23384;&#19979;&#19968;&#20010;node&#30340;&#20301;&#32622;
+            if not new_head:
+                new_node = node
+            else:
+                new_tail.next = node
+            new_tail = node
+            new_tail.next = None
+            node = prev.next
+        return new_head
