复杂链表的复制

题目

牛客网

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的 head 。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

解题思路

  1. 复制每个节点,如:复制节点 A 得到 A1 ,将 A1 插入节点 A 后面
  2. 遍历链表,并将 A1->random = A->random->next;
  3. 将链表拆分成原链表和复制后的链表
public RandomListNode Clone(RandomListNode pHead) {
    if (pHead == null) {
        return null;
    }

    RandomListNode cursor = pHead;
    while (cursor != null) {
        RandomListNode copyNode = new RandomListNode(cursor.label);

        RandomListNode nextNode = cursor.next;
        cursor.next = copyNode;
        copyNode.next = nextNode;

        cursor = nextNode;
    }

    cursor = pHead;
    while (cursor != null) {
        RandomListNode copyNode = cursor.next;

        if (cursor.random == null) {
            cursor = copyNode.next;
            continue;
        }

        copyNode.random = cursor.random.next;

        cursor = copyNode.next;
    }

    RandomListNode copyHead = pHead.next;
    cursor = pHead;
    while (cursor.next != null) {
        RandomListNode copyNode = cursor.next;
        cursor.next = copyNode.next;
        cursor = copyNode;
    }

    return copyHead;
}