剑指offer 35题:复杂链表的复制
2019-01-08 本文已影响0人
灰化肥发黑会挥发
题目:请实现一个函数,复杂一个复杂链表,在复杂链表中,每个节点除了有一个m_pNext指针指向下一个节点,还有一个m_pSibling指针指向链表中的任意节点或者nullptr。
- 思路1:首先复制m-pNext,然后再复制m-pSibling,但是在复制的过程中,需要查找m-pSibling,时间复杂度为O(n_{2})
- 思路2:上一步主要的时间复杂度是查找,很自然的想到使用能够map来进行从查找,时间复杂度为O(1),存储(原始节点,复制的节点)
- 思路3:如果将需要复制的节点复制在原始节点之后,m_pSibling对应也是在后面,找起来比较快,然后再将这个链表拆分。时间复杂度为O(n)
public class ComplexListNodeCloneSolution {
public void ComplexListNodeClone(ComplexListNode phead){
if(phead==null) return;
ComplexListNode node = phead;
while(node!=null){
ComplexListNode newNode = new ComplexListNode(node.val);
newNode.next = node.next;
node.next = newNode;
node = node.next;
newNode.sibling = null;
}
node = phead;
while(node!=null){
if(node.sibling!=null) node.next = node.sibling.next;
node = node.next;
}
node = phead;
while(node!=null){
// 链表拆分
}
}
}