题目描述
blablabla
样例
blablabla
算法1
() $O(n^2)$
blablabla
时间复杂度分析:blablabla
Python 代码
# Definition for singly-linked list with a random pointer.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return head
node = head
# get a double length link
while node:
tmp = ListNode(node.val)
tmp.next = node.next
node.next = tmp
node = tmp.next
# copy the random attribute
node = head
while node:
if node.random:
node.next.random = node.random
else:
node.next.random = None
node = node.next.next
# get the final linklist
node = head.next # node is the copied linklist
while node.next:
tmp = node.next.next
node.next = node.next.next
node = tmp
return head.next
老哥你还在吗,这个代码好像不能AC,(不能修改原链表)
可能是y神加强了test case