复制带随机指针的链表 · Copy List with Random Pointer
2024-08-28 20:16:58
[抄题]:
给出一个链表,每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
[思维问题]:
[一句话思路]:
完完全全地复制,否则不好操作。
1->1`->2->2`->3->3`->4->4` 紧随其后地复制,再拆开
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- newNode是每次新建的节点,不用往后移。head每次要移动2格,才能复制。
- head = head.next.next意在往下走,temp.next = temp.next.next;意在往下连
- if中非空的条件都是指针:if (head.next.random != null)
- RandomListNode newHead = new RandomListNode(head.label);表示有角标的从属关系
- split用的是快慢指针的思想,temp head分别连接即可(用temp是为了写法更简单):
while (head != null) {
RandomListNode temp = head.next;暂存
head = temp.next;连接head
if (temp.next != null) {连接temp
temp.next = temp.next.next;
}
} - 主函数里要写corner case :if (head == null) { return null; }
[二刷]:
- head.random.next是个数 = head.next.random是个指针;重点看最后一位
- splitList里面要用while循环,一直split
- head往后移动时,是head本身 = temp.next;
- 又不记得写corner case了,唉
[总结]:
[复杂度]:Time complexity: O(n) Space complexity: O(1)
[英文数据结构,为什么不用别的数据结构]:
[其他解法]:
哈希彪
[Follow Up]:
[题目变变变]:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @param head: The head of linked list with a random pointer.
* @return: A new head of a deep copy of the list.
*/
private void copyNext(RandomListNode head) {
while (head != null) {
RandomListNode newHead = new RandomListNode(head.label);
newHead.next = head.next;
newHead.random = head.random;
head.next = newHead;
head = head.next.next;
}
} private void copyRandom(RandomListNode head) {
while (head != null) {
if (head.next.random != null) {
head.next.random = head.random.next;
}
head = head.next.next;
}
} private RandomListNode splitList(RandomListNode head) {
RandomListNode newHead = head.next;
while (head != null) {
RandomListNode temp = head.next;
head.next = temp.next;
head = head.next;
if (temp.next != null) {
temp.next = temp.next.next;
}
}
return newHead;
} public RandomListNode copyRandomList(RandomListNode head) {
copyNext(head);
copyRandom(head);
return splitList(head);
}
}
最新文章
- android:使用Messenger进行进程间通信(一)
- 大家一起和snailren学java-(四)初始化与清理
- [css] line boxes
- TableViewCell自定义分割线
- TP复习11
- Hibernate(八)一对多单向关联映射
- A - Fire Net - hdu 1045(二分图匹配)
- CentOS yum安装配置lnmp服务器(Nginx+PHP+MySQL)
- java oop详解
- OOP的基本原则
- hadoop启动 datanode的live node为0
- 设置MyBatis在控制台打印SQL语句
- AutoMapper中用户自定义转换
- win10上VMare安装Centos7并使用Xshell连接Centos
- rsync实现文件同步
- 以太坊私有链POA模式
- 搭建Linux-java web运行环境之一:安装jdk+tomcat
- jekins 实现Django项目的自动部署(ubuntu16.04,python2.7,django1.11)
- 编码CODING
- asp.netMVC中权限控制论
热门文章
- Linux系统查看系统硬件配置信息
- 简单学习Git
- jap -文档 https://www.tutorialspoint.com/jpa/jpa_jpql.htm
- mysql 5.7新特新 操作json 数组
- HTML5 浏览器接收的常用 content-type
- leetcode202
- 22.OGNL与ValueStack(VS)-默认类Math的访问
- unity WWW加载进度条
- sqlcmd导入大数据文件
- C++ 11 中的 Lambda 表达式的使用