题目描述
请实现一个函数可以复制一个复杂链表。
在复杂链表中,每个结点除了有一个指针指向下一个结点外,还有一个额外的指针指向链表中的任意结点或者null。
注意:
函数结束后原链表要与输入时保持一致。
复制节点 法
public ListNode copyRandomList(ListNode head) {
if(head == null) return null;
ListNode dummy = new ListNode(-1);
dummy.next = head;
while (head != null) {
ListNode next = head.next;
ListNode newHead = new ListNode(head.val);
head.next = newHead;
newHead.next = next;
head = head.next.next;
}
head = dummy.next;
while (head != null) {
if(head.random == null) head.next.random = null;
else{
head.next.random = head.random.next;
}
head = head.next.next;
}
head = dummy.next;
ListNode newHead = head.next;
ListNode res = newHead;
while(head != null) {
ListNode next = head.next.next;
head.next = next;
head = head.next;
if(head!=null){
newHead.next = next.next;
newHead = newHead.next;
}
}
head = dummy.next;
dummy.next = null;
return res;
}