LeetCode|【LeetCode】138. Copy List with Random Pointer 解题报告（Python） LeetCode|算法

【LeetCode|【LeetCode】138. Copy List with Random Pointer 解题报告（Python）】作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/copy-list-with-random-pointer/description/
题目描述 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
题目大意复制一个复杂链表，这个复杂链表是指出了值和next指针外，还有一个random指针可能指向任何位置的链表节点或空。
解题方法这个题是剑指Offer的“面试题26：复杂链表的复制”原题。书上的做法是在原先的每个节点之后进行复制了一个节点，从而构成了一个二倍长度的单链表，然后再修改random指针。总之很麻烦。
更好地一个做法是使用hashtable，在这个hash表里，记录了老链表和新链表的每一组对应。这样先构造了一个纯next的链表，然后再次循环就能得到带random的链表了。

""" # Definition for a Node. class Node(object): def __init__(self, val, next, random): self.val = val self.next = next self.random = random """ class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ nodeDict = dict() dummy = Node(0, None, None) nodeDict[head] = dummy newHead, pointer = dummy, head while pointer: node = Node(pointer.val, pointer.next, None) nodeDict[pointer] = node newHead.next = node newHead, pointer = newHead.next, pointer.next pointer = head while pointer: if pointer.random: nodeDict[pointer].random = nodeDict[pointer.random] pointer = pointer.next return dummy.next

日期 2018 年 6 月 23 日 —— 美好的周末要从刷题开始