JZ25-复杂链表的复制
复杂链表的复制
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
// 插入新节点
RandomListNode cur = pHead;
while (cur != null) {
RandomListNode clone = new RandomListNode(cur.label);
clone.next = cur.next;
cur.next = clone;
cur = clone.next; //跳到原链表的下一个节点，既clone.next
}
// 建立 random 链接
cur = pHead; //从头开始重新遍历
while (cur != null) {
RandomListNode clone = cur.next;
if (cur.random != null) {
clone.random = cur.random.next;
}
cur = clone.next;
}
// 拆分
cur = pHead;
RandomListNode cloneHead = pHead.next;
while (cur.next != null) { //这个cur是对所有的节点来说，包括clone...cur可以指原节点，也可以指向clone节点
//最后一个原节点和clone节点，不用再连接
RandomListNode next = cur.next;
cur.next = next.next;
cur = next;
}
return cloneHead;
}
}
class Solution2 {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode cloneHead = new RandomListNode(pHead.label);
RandomListNode temp = cloneHead; //为了让cloneHead可以返回，保存头节点
while (pHead.next != null) {
temp.next = new RandomListNode(pHead.next.label);
if (pHead.random != null) {
temp.random = new RandomListNode(pHead.random.label);
}
pHead = pHead.next;
temp = temp.next;
}
return cloneHead;
}
} 
