题解 | #复杂链表的复制#

package main

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

/**
 *
 * @param pHead RandomListNode类
 * @return RandomListNode类
*/
func Clone( head *RandomListNode ) *RandomListNode {
    //write your code here
    // 1. 克隆链表
    cloneNode(head)
    // 2. 链接 random 指针
    connectRandomLink(head)
    // 3. 拆分链表
    return ReconnectLinkList(head)
}

func cloneNode(head *RandomListNode) {
    head1 := head
    for head1 != nil {
        clone := &RandomListNode{
            Label: head1.Label,
            Next: head1.Next,
        }
        head1.Next = clone
        head1 = clone.Next
    }
}

func connectRandomLink(head *RandomListNode) {
    head1 := head

    for head1 != nil {
        clone := head1.Next
        if head1.Random != nil {
            clone.Random = head1.Random.Next
        }
        head1 = clone.Next
    }
}

func ReconnectLinkList(head *RandomListNode) *RandomListNode {
    head1 := head
    var cloneHead *RandomListNode
    // clone head
    if head1 != nil {
        cloneHead  = head1.Next
        head1.Next = cloneHead.Next
        head1 = head1.Next
    }

    cloneNode := cloneHead
    for head1 != nil {
        cloneNode.Next = head1.Next
        cloneNode = cloneNode.Next
        head1.Next = cloneNode.Next
        head1 = head1.Next
    }
    return cloneHead
}

part1 ：克隆链表，为每一个节点克隆一个节点并将其插入到旧节点之后；

part2：为每一个新节点链接 random 指针；

part3：将链表拆分为新旧两个链表，返回新链表的头指针。