138_复制带随机指针的链表
package 链表; import java.util.HashMap; import java.util.Map; public class _138_复制带随机指针的链表 { class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } //方法一:使用递归+ hashMap (因为随机指针:一个节点可能被多个其他节点指向) /** hashMpa 避免重复创建 **/ /** * ,当我们拷贝节点时,「当前节点的随机指针指向的节点」可能还没创建,因此我们需要变换思路。一个可行方案是,我们利用回溯的方式,让每个节点的拷贝操作相互独立。 */ Map<Node, Node> cachedNode = new HashMap<Node, Node>(); public Node copyRandomList(Node head) { if (head == null) { return null; } if (!cachedNode.containsKey(head)) { Node headNew = new Node(head.val); cachedNode.put(head, headNew); headNew.next = copyRandomList(head.next); headNew.random = copyRandomList(head.random); } return cachedNode.get(head); } /** * 间隔插秧法啦(把秧苗插进来后,以前是走一步,现在多了一个结点要多走一步) * 第一步:插入苗 * 第二步:先处理随机指针的复制(原本有随机、next的复制都需要处理?):优先处理随机(之所以要把苗插入,就是为了实现在同一流水线具有同一规则,如果先处理next 导致已经变成两条链表了,拿不到随机了) * @author Huangyujun * */ class Solution2 { public Node copyRandomList(Node head) { if (head == null) { return null; } //第一步:插入苗 for (Node node = head; node != null; node = node.next.next) { Node nodeNew = new Node(node.val); nodeNew.next = node.next; node.next = nodeNew; } //第二步:先处理随机指针的复制(利用的是原来的链表非常方便的找到随机,而插入的苗的随机就是在原来的基础+1 【node.random.next】) for (Node node = head; node != null; node = node.next.next) { Node nodeNew = node.next; nodeNew.random = (node.random != null) ? node.random.next : null; } //第三步:处理next 指针的复制 Node headNew = head.next; for (Node node = head; node != null; node = node.next) { Node nodeNew = node.next; node.next = node.next.next; nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null; } return headNew; } } }