/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */
/**
* 根据每个节点n复制其节点为n‘,并放在节点n的后面
*/
public class Solution { public RandomListNode Clone(RandomListNode pHead) { CloneListNode(pHead); ConnectSiblingNode(pHead); return getClone(pHead); }
/**
* 将链表拆分
* @param pHead
* @return
*/
public RandomListNode getClone(RandomListNode pHead) { RandomListNode pNode=pHead; RandomListNode pCloneNode = null; RandomListNode pCloneHead = null; if(pNode!=null){ pCloneNode = pCloneHead = pNode.next; //pCloneNode = pNode.next; pNode.next = pCloneNode.next; pNode = pNode.next; } while(pNode!=null){ pCloneNode.next = pNode.next; pCloneNode = pCloneNode.next; pNode.next = pCloneNode.next; pNode = pNode.next; } return pCloneHead; } //复制随机相连的节点 public void ConnectSiblingNode(RandomListNode pHead) { RandomListNode pNode=pHead; while (pNode!=null){ RandomListNode pCloneNode = pNode.next; if(pNode.random!=null){ pCloneNode.random = pNode.random.next; } pNode = pCloneNode.next; } } //复制直接相连的节点 public void CloneListNode(RandomListNode pHead) { RandomListNode pNode=pHead; while (pNode!=null){ RandomListNode pCloneNode = new RandomListNode(0); pCloneNode.label = pNode.label; pCloneNode.next = pNode.next; // pCloneNode.random = null; //pNode.next = pCloneNode; pNode.next = pCloneNode; pNode = pCloneNode.next; } } }
原文:https://www.cnblogs.com/q-1993/p/10745744.html