首页 > 代码库 > 【LeetCode】Copy List with Random Pointer
【LeetCode】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.
解答题目要求拷贝一个链表,该链表除了一个next指针外还有一个随机指针。
方法1:可以通过三步实现拷贝,a.在原链表插入拷贝节点,b.复制随机指针,c.分解成两个独立的链表
方法2:使用Hash表的做法,先依次遍历原链表,每经过一个节点X,开辟一个新节点Y,然后(key=X的地址,value=http://www.mamicode.com/Y的地址)存入哈希表。第二次再遍历原链表,根据拓扑结构设置新的链表。需要O(n)的空间,时间也是O(n)。
/** * 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 { public RandomListNode copyRandomList(RandomListNode head) { if(head==null){ return null; } RandomListNode p=head; //copy every node and insert to list while(p!=null){ RandomListNode copy=new RandomListNode(p.label); copy.next=p.next; p.next=copy; p=copy.next; } //copy random pointer for each new node p=head; while(p!=null){ if(p.random!=null){ p.next.random=p.random.next; } p=p.next.next; } //break list to two //只要断开连接的next指针即可,random不变 p=head; RandomListNode newHead=head.next; while(p!=null){ RandomListNode temp=p.next; p.next=temp.next; if(temp.next!=null){ temp.next=temp.next.next; } p=p.next; } return newHead; } } //方法2,利用HashMap public RandomListNode copyRandomList(RandomListNode head){ if(head==null){ return null; } HashMap<RandomListNode,RandomListNode> map=new HashMap<RandomListNode,RandomListNode>(); RandomListNode newHead=new RandomListNode(head.label); RandomListNode p=head; RandomListNode q=newHead; map.put(head,newHead); p=p.next; while(p!=null){ RandomListNode temp=new RandomListNode(p.label); map.put(p,temp); q.next=temp; q=temp; p=p.next; } p=head; q=newHead; while(p!=null){ if(p.random!=null){ q.random=map.get(p.random); }else{ q.random=null; } p=p.next; q=q.next; } return newHead; }
---EOF---
【LeetCode】Copy List with Random Pointer
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。