数据结构与算法--实现链表的复制(链表中节点比较特殊,含有一个rand指针,指向任意一个节点)
已在leetcode上执行通过
// https://leetcode.com/problems/copy-list-with-random-pointer/ leetcode地址
public class CopyListWithRandom {
public static class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public static Node copyRandomList2(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next;
while (cur != null){
next = cur.next;
Node tmp = new Node(cur.val);
cur.next = tmp;
tmp.next = next;
cur = next;
}
cur = head;
Node curNext;
while (cur != null){
curNext = cur.next;
next = cur.next.next;
Node rand = cur.random;
//curNext.random = rand.next;
curNext.random = rand != null ? rand.next : null;
cur = next;
}
cur = head;
Node newHead = cur.next;
while (cur != null){
curNext = cur.next;
next = cur.next.next;
cur.next = next;
if(next != null) {
curNext.next = next.next;
}
cur = next;
}
return newHead;
}
}