问题描述
- public class Node {
- public int val;
- public Node next;
- public Node rand;
- public Node(int data) {
- this.val=data;
- }
- }
Node 类中的 value 是节点值, next 指针和正常单链表中 next 指针的意义一样, 都指向下一个节点, rand 指针是 Node 类中新增的指针, 这个指针可能指向链表中的任意一个节点, 也可能指向 null.
给定一个由 Node 节点类型组成的无环单链表的头节点 head, 请实现一个函数完成这个链表中所有结构的复制, 并返回复制的新链表的头节点.
进阶: 不使用额外的数据结构, 只用有限几个变量, 且在时间复杂度为 O(N) 内完成原问题要实现的函数.
题解
方法一:
使用哈希表.
时间复杂度 O(n), 额外空间复杂度 O(n)
方法二:
todo
代码 (方法一)
- import java.util.HashMap;
- public class Main {
- public static void main(String args[]) {
- Node n1=new Node(1);
- Node n2=new Node(2);
- Node n3=new Node(3);
- Node n4=new Node(4);
- Node n5=new Node(5);
- n1.next=n2;
- n2.next=n3;n2.rand=n1;
- n3.next=n4;
- n4.next=n5;n4.rand=n5;
- Node head=n1;
- Node newHead=copyRandList(head);
- Node p=newHead;
- while(p.next!=null) {
- System.out.println(p.val);
- System.out.println(p.rand);
- p=p.next;
- }
- }
- public static Node copyRandList(Node head){
- HashMap<Node, Node> map=new HashMap<Node, Node>();
- Node cur=head;
- while(cur != null){
- map.put(cur, new Node(cur.val));
- 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);
- }
- }
[程序员代码面试指南] 链表问题 - 复制含有随机指针节点的链表 (方法二待做)
来源: http://www.bubuko.com/infodetail-3065419.html