[leetcode]Copy List with Random Pointer @ Python
2024-10-14 16:14:05
原题地址:https://oj.leetcode.com/problems/copy-list-with-random-pointer/
题意:
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.
解题思路:这题主要是需要深拷贝。看图就明白怎么写程序了。
首先,在原链表的每个节点后面都插入一个新节点,新节点的内容和前面的节点一样。比如上图,1后面插入1,2后面插入2,依次类推。
其次,原链表中的random指针如何映射呢?比如上图中,1节点的random指针指向3,4节点的random指针指向2。如果有一个tmp指针指向1(蓝色),则一条语句:tmp.next.random = tmp.random.next;就可以解决这个问题。
第三步,将新的链表从上图这样的链表中拆分出来。
代码:
# Definition for singly-linked list with a random pointer.
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None class Solution:
# @param head, a RandomListNode
# @return a RandomListNode
def copyRandomList(self, head):
if head == None: return None
tmp = head
while tmp:
newNode = RandomListNode(tmp.label)
newNode.next = tmp.next
tmp.next = newNode
tmp = tmp.next.next
tmp = head
while tmp:
if tmp.random:
tmp.next.random = tmp.random.next
tmp = tmp.next.next
newhead = head.next
pold = head
pnew = newhead
while pnew.next:
pold.next = pnew.next
pold = pold.next
pnew.next = pold.next
pnew = pnew.next
pold.next = None
pnew.next = None
return newhead
最新文章
- JavaScript标准库之——JSON
- ie8下使用knockoutjs遇到的一个模板异常
- Python字符串基础一
- 快消零售行业怎么用K2做开关店管理?
- Spring 依赖注入,在Main方法中取得Spring控制的实例
- linux下udp编程
- MongoDB (十一) MongoDB 排序文档
- Fragment碎片频繁来回切换的时候报java.lang.IllegalStateException: No activity
- 简单的js反选,全选,全不选
- Ajax 介绍
- Spring Boot简介
- ValueError: 'format' in __slots__ conflicts with class variable
- Oracle debug
- laravel 常见问题
- 机器学习linux系统环境安装
- APM的3DR无线数传的安装和调试
- 再学Java 之 HashMap的底层实现
- Eclipse更改皮肤
- Vue 入门之数据绑定
- 企业级镜像管理系统Harbor
热门文章
- Servlet中保存的cookie值读取不到
- 【AI in 美团】深度学习在OCR中的应用
- python获取文件属性
- 选择 React Native 的理由
- [leetcode trie]208. Implement Trie (Prefix Tree)
- python opencv3 检测人
- 基于ONVIF协议的摄像头开发总结
- [LOJ2541][PKUWC2018]猎人杀(容斥+分治+FFT)
- [BZOJ4850][JSOI2016]灯塔(分块/决策单调性优化DP)
- 浅谈期望的线性性(可加性)【CodeForces280c】【bzoj3036】【bzoj3143】