复杂链表的复制

1. 题目描述

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

2. 思路

先复制节点到原有节点的后面，然后复制随机指针，最后拆分链表

3. 实现

• java

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

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


public class 复杂链表的复制
{
    public RandomListNode Clone(RandomListNode pHead)
    {
        //检查参数
        if (pHead == null)
        {
            return null;
        }
        //遍历一遍复制所有节点到源节点的后面
        RandomListNode current = pHead;
        while (current != null)
        {
            //先新建节点
            RandomListNode newNode = new RandomListNode(current.label);
            newNode.next = current.next;
            //修改上一个节点的指针
            current.next = newNode;
            //继续下一个
            current = newNode.next;
        }
        //再遍历一遍复制随机节点
        current = pHead;
        while (current != null)
        {
            //复制随机指针
            if (current.random != null)
            {
                current.next.random = current.random.next;
            }
            //继续下一个
            current = current.next.next;
        }
        //再遍历一遍拆分链表
        current = pHead;
        RandomListNode newHead = current.next;
        RandomListNode current2 = newHead;
        while (current != null)
        {
            //拆分
            current.next = current.next.next;
            if (current2.next != null)
            {
                current2.next = current2.next.next;
            }

            //继续下一个
            current = current.next;
            current2 = current2.next;
        }

        return newHead;
    }
}

• go

type RandomListNode struct {
	Label  int
	Next   *RandomListNode
	Random *RandomListNode
}

/**
 *
 * @param pHead RandomListNode类
 * @return RandomListNode类
 */
//时间:O(n)
//空间:O(1)
func Clone(head *RandomListNode) *RandomListNode {
	if head == nil {
		return nil
	}
	//遍历一遍复制next
	current := head
	for current != nil {
		newNode := &RandomListNode{
			Label:  current.Label,
			Next:   current.Next,
			Random: current.Random,
		}
		current.Next = newNode
		current = newNode.Next
	}
	//遍历一遍复制random
	current = head
	for current != nil{
		if current.Random != nil {
			current.Next.Random = current.Random.Next
		}
		current = current.Next.Next
	}

	//拆分
	current = head
	newHead := head.Next
	current2 := newHead
	for current != nil {
		current.Next = current.Next.Next
		if current2.Next != nil {
			current2.Next = current2.Next.Next
		}

		current = current.Next
		current2 = current2.Next
	}

	return newHead
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    if head == nil {return nil}
    
    current := head
    for current != nil {
        next := current.Next
        newNode := &Node{Val:current.Val, Next:next}
        current.Next = newNode
        current = next
    }

    current = head
    for current != nil {
        next := current.Next.Next
        if current.Random != nil {current.Next.Random = current.Random.Next}
        current = next
    }

    current = head
    newHead := current.Next
    current2 := newHead
    for current != nil {
        current.Next = current.Next.Next
        if current2.Next != nil {current2.Next = current2.Next.Next}
        current = current.Next
        current2 = current2.Next
    }
    return newHead
}

4. 参考

• 复杂链表的复制_牛客网
• 剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）