Copy Complex Linked List

1. Problem Description

Given a complex linked list (each node contains a node value and two pointers, one pointing to the next node and another special pointer pointing to any node), return the head of the copied complex linked list. (Note: do not return references to nodes from the input parameters in the output, otherwise the judge will directly return empty.)

2. Approach

First copy each node after the original node, then copy the random pointers, and finally split the linked list.

3. Implementation

• java

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

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


public class 复杂链表的复制
{
    public RandomListNode Clone(RandomListNode pHead)
    {
        // Check parameters
        if (pHead == null)
        {
            return null;
        }
        // Traverse once and copy every node after its source node
        RandomListNode current = pHead;
        while (current != null)
        {
            // Create the new node first
            RandomListNode newNode = new RandomListNode(current.label);
            newNode.next = current.next;
            // Modify the previous node's pointer
            current.next = newNode;
            // Continue to the next one
            current = newNode.next;
        }
        // Traverse again to copy random pointers
        current = pHead;
        while (current != null)
        {
            // Copy the random pointer
            if (current.random != null)
            {
                current.next.random = current.random.next;
            }
            // Continue to the next one
            current = current.next.next;
        }
        // Traverse again to split the linked list
        current = pHead;
        RandomListNode newHead = current.next;
        RandomListNode current2 = newHead;
        while (current != null)
        {
            // Split
            current.next = current.next.next;
            if (current2.next != null)
            {
                current2.next = current2.next.next;
            }

            // Continue to the next one
            current = current.next;
            current2 = current2.next;
        }

        return newHead;
    }
}

• go

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

/**
 *
 * @param pHead RandomListNode class
 * @return RandomListNode class
 */
// Time: O(n)
// Space: O(1)
func Clone(head *RandomListNode) *RandomListNode {
	if head == nil {
		return nil
	}
	// Traverse once to copy next
	current := head
	for current != nil {
		newNode := &RandomListNode{
			Label:  current.Label,
			Next:   current.Next,
			Random: current.Random,
		}
		current.Next = newNode
		current = newNode.Next
	}
	// Traverse once to copy random
	current = head
	for current != nil{
		if current.Random != nil {
			current.Next.Random = current.Random.Next
		}
		current = current.Next.Next
	}

	// Split
	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. References

• Copy a Complex Linked List - NowCoder
• Sword Offer 35. Copy a Complex Linked List - LeetCode