复制含有随机指针节点的链表
原创
一.复制含有随机指针节点的链表
【 题目】 一种特殊的链表节点类描述如下：
public class Node {
public int value; public Node next;
public Node rand;
public Node(int data) { this.value = data; }
}Node类中的value是节点值， next指针和正常单链表中next指针的意义一 样， 都指向下一个节点， rand指针是Node类中新增的指针， 这个指针可 能指向链表中的任意一个节点， 也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点head， 请实现一个 函数完成这个链表中所有结构的复制， 并返回复制的新链表的头节点。 进阶：不使用额外的数据结构， 只用有限几个变量， 且在时间复杂度为 O(N)内完成原问题要实现的函数。
解法一：
采用的是HaspMap()，空间复杂度为O(N)，通过map把原始链表和新链表关联起来。
public static Node copyListWithRand1(Node head) {
if (head == null) return head;
HashMap<Node,Node> map = new HashMap<>();
Node cur = head;
while (cur != null){
map.put(cur,new Node(cur.value));
cur = cur.next;
}
cur = head;
while (cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}解法二：
public static Node copyListWithRand2(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
//生成节点
while (cur != null){
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
//处理rand指针
while (cur != null){
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand == null ? null : cur.rand.next;
cur = next;
}
Node res = head.next;
cur = head;
//拆分
while (cur != null){
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录