首页 > itarticle > 【剑指offer】复杂链表的复制

【剑指offer】复杂链表的复制

admin 11月 13, 2020 0

题目

请实现函数ComplexListNode Clone(ComplexListNode pHead)，复制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任意结点或者NULL。

实现

public class  {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

public RandomListNode Clone(RandomListNode pHead) {
    CloneNodes(pHead);
    ConnectSiblingNodes(pHead);
    return ReconnectNodes(pHead);
}

private void CloneNodes(RandomListNode pHead) {
    RandomListNode node = pHead;

    while (node != null) {
        RandomListNode clone = new RandomListNode(node.label);
        clone.next = node.next;
        node.next = clone;
        node = clone.next;
    }
}

private void ConnectSiblingNodes(RandomListNode pHead) {
    RandomListNode node = pHead;

    while (node != null) {
        if (node.random != null)
            node.next.random = node.random.next;

        node = node.next.next;
    }
}

private RandomListNode ReconnectNodes(RandomListNode pHead) {
    RandomListNode node = pHead;
    RandomListNode cloneNode = null, cloneHead = null;

    if (node != null) {
        cloneHead = cloneNode = node.next;
        node.next = cloneNode.next;
        node = node.next;
    }

    while (node != null) {
        cloneNode.next = node.next;
        cloneNode = cloneNode.next;
        node.next = cloneNode.next;
        node = node.next;
    }
    
    return cloneHead;
}