美文网首页
剑指offer 35题:复杂链表的复制

剑指offer 35题:复杂链表的复制

作者: 灰化肥发黑会挥发 | 来源:发表于2019-01-08 08:36 被阅读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){
//            链表拆分
        }
    }
}

相关文章

网友评论

      本文标题:剑指offer 35题:复杂链表的复制

      本文链接:https://www.haomeiwen.com/subject/dggmrqtx.html