面试题35：复杂链表的复制.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目描述\n",
    "输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空)\n",
    "\n",
    "### 题目理解\n",
    "这题的意思实际上是要求复制这个复杂链表。一般的思路都是，先复制这个链表的下一个结点，然后重新遍历，寻找这个链表的随机指向的结点。但是，由于随机指向的结点有可能在这个结点的前面，也有可能在这个结点的后面，所以就需要重新再过一遍链表才能找到那个结点。这就需要消耗$O(n^2)$的复杂度。书中主要介绍了一种更为简单的数据结构。\n",
    "\n",
    "### 书中的思路\n",
    "如果每次都循环找没有被指向的结点，复杂度会变成$O(n^2)$,所以书上给出了一种优化思路。\n",
    "\n",
    "1. 使用哈希表。在每次复制结点的时候，记录$<N,N'>$点对，这样才可以快速定位。\n",
    "2. 把复制的结点插入到原节点中。这样也可以快速定位随机指向的点。后面只需要从链表中每隔两个取值即可。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -*- coding:utf-8 -*-\n",
    "class RandomListNode:\n",
    "    def __init__(self, x,nxt = None, random = None):\n",
    "        self.label = x\n",
    "        self.next = nxt\n",
    "        self.random = random\n",
    "class Solution:\n",
    "    # 返回 RandomListNode\n",
    "    def Clone(self, pHead):\n",
    "        # write code here\n",
    "        self.CloneNodes(pHead)\n",
    "        self.ConnectSiblingNodes(pHead)\n",
    "        return self.ReconnectNodes(pHead)\n",
    "    \n",
    "    def CloneNodes(self,pHead):\n",
    "        pNode = pHead\n",
    "        while pNode is not None:\n",
    "            pCloned = RandomListNode(pNode.label)\n",
    "            pCloned.next = pNode.next\n",
    "            pCloned.random = None\n",
    "        \n",
    "            pNode.next = pCloned\n",
    "            pNode = pCloned.next\n",
    "    \n",
    "    def ConnectSiblingNodes(self,pHead):\n",
    "        pNode = pHead\n",
    "        while pNode is not None:\n",
    "#             print(pNode.label)\n",
    "            if pNode.random is not None:\n",
    "                pNode.next.random = pNode.random.next\n",
    "            pNode = pNode.next.next\n",
    "    \n",
    "    def ReconnectNodes(self, pHead):\n",
    "        ### 这一步把原始的pHead的结构给搞坏掉了- -\n",
    "        pNode = pHead\n",
    "        if pNode is not None:\n",
    "            pCloned = pNode.next\n",
    "            pClonedHead = pCloned\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "        while pNode is not None:\n",
    "            pNode.next = pCloned.next\n",
    "            pNode = pNode.next\n",
    "            if pNode is None:\n",
    "                break\n",
    "            pCloned.next = pNode.next\n",
    "            pCloned = pCloned.next\n",
    "        return pClonedHead\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [],
   "source": [
    "### test \n",
    "### 构造一个随机表\n",
    "test4 = RandomListNode(4)\n",
    "test3 = RandomListNode(3,test4)\n",
    "test2= RandomListNode(2,test3,test4)\n",
    "test1 = RandomListNode(1,test2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = Solution()\n",
    "res = a.Clone(test1)\n",
    "node = res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 <__main__.RandomListNode object at 0x0000022CC5DA3588> None\n",
      "2 <__main__.RandomListNode object at 0x0000022CC5DA3BE0> <__main__.RandomListNode object at 0x0000022CC5DA3A20>\n",
      "3 <__main__.RandomListNode object at 0x0000022CC5DA3A20> None\n",
      "4 None None\n"
     ]
    }
   ],
   "source": [
    "# 测试复制的链表\n",
    "while node is not None:\n",
    "    print(node.label,node.next,node.random)\n",
    "    node = node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 <__main__.RandomListNode object at 0x0000022CC5DA34E0> None\n",
      "2 <__main__.RandomListNode object at 0x0000022CC5DA3470> <__main__.RandomListNode object at 0x0000022CC5DA3A90>\n",
      "3 <__main__.RandomListNode object at 0x0000022CC5DA35C0> None\n",
      "4 <__main__.RandomListNode object at 0x0000022CC5DA3A90> None\n"
     ]
    }
   ],
   "source": [
    "# 测试原始链表\n",
    "node2 = test1\n",
    "while node2 is not None:\n",
    "    print(node2.label,node2,node2.random)\n",
    "    node2 = node2.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}