一种特殊的单链表节点类型描述如下：
public static class Node{ public int value; public Node next; public Node rand; public Node(int v) { value=v; } }
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。要求：时间复杂度O(N)，额外空间复杂度O(1)，注意，无环是指next方向上是无环的！！！
方法一（笔试用，最简单）：在next方向上正常遍历一遍链表，遍历过程种将每个结点克隆存入HashMap<Node,Node>，表中的key是老结点，value是克隆的结点。就是人为构造一种对应关系，之后再遍历一遍链表，便可实现，具体看下面代码。但是这种方法在空间复杂度上没有做到O(1)
方法二（面试用）：额外空间复杂度O(1)，具体看代码
package com.harrison.class06; import java.util.HashMap; public class Code04_CopyListWithRandom { public static class Node { public int value; public Node next; public Node rand; public Node(int v) { value = v; } } public static Node copyRandomList1(Node head) { HashMap<Node, Node> map = new HashMap<Node, Node>(); Node cur = head; while (cur != null) { map.put(cur, new Node(cur.value)); cur = cur.next; } cur = head; while (cur != null) { // cur (key)老结点 map.get(cur) (value)新结点 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 copyRandomList2(Node head) { if (head == null) { return null; } // 1 -> 2 -> 3 -> null // 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null Node cur = head;// 老结点 Node next = null;// 老结点的下一个结点 while (cur != null) { next = cur.next;// next记住老结点的下一个结点 cur.next = new Node(cur.value);// 当前的老结点指向 复制自己的结点 cur.next.next = next;// 复制的结点指向 next cur = next; } cur = head; Node copy = null;// 复制的结点 // 依次设置 1' 2' 3' 的rand指针 while (cur != null) { next = cur.next.next;// next 记住老结点的下一个结点 copy = cur.next;// copy 来到(第一个)复制的结点 // copy结点的rand指针指向 老结点的rand指针指向的结点的next指针 copy.rand = cur.rand != null ? cur.rand.next : null; cur = next;// 当前结点往下跳 } Node res = head.next;// 记住复制后的链表的头结点 cur = head; // next方向上，把新老链表分离，rand方向不要动 while (cur != null) { next = cur.next.next;// next 记住老结点的下一个结点 copy = cur.next;// copy 来到(第一个)复制的结点 // copy结点的next指针指向 下一个老结点的next指针 copy.next = next != null ? next.next: null; cur = next;// 当前结点往下跳 } return res; } public static void printLinkedList(Node node) { System.out.print("Linked List："); while (node != null) { System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { Node head1 = new Node(7); head1.next = new Node(9); head1.next.next = new Node(1); head1.next.next.next = new Node(8); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(2); head1.next.next.next.next.next.next = new Node(5); printLinkedList(head1); //head1=copyRandomList1(head1); head1 = copyRandomList2(head1); printLinkedList(head1); } }
