138. 复制带随机指针的链表
类似于 133. 克隆图 但是由于random节点的存在不能够直接找random的节点。这里用了拆分链表的方法:
- 创建小弟节点
- 链接random节点
- 拆分大哥小弟
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
// 复制小弟:
for(Node oldBrother = head; oldBrother!=null; oldBrother = oldBrother.next.next){
Node youngBrother = new Node(oldBrother.val);
youngBrother.next = oldBrother.next;
oldBrother.next = youngBrother;
}
// 复制random结点:
for(Node oldBrother = head; oldBrother!=null; oldBrother = oldBrother.next.next){
if(oldBrother.random!=null) oldBrother.next.random = oldBrother.random.next;
}
// 拆分大哥小弟两链表:
Node dummy = new Node(-1), cur = dummy;
for(Node oldBrother = head; oldBrother!=null; oldBrother = oldBrother.next){
Node youngBrother = oldBrother.next;
cur = cur.next = youngBrother;
oldBrother.next = youngBrother.next;
}
return dummy.next;
}
}