JZ25 复杂链表的复制

复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：1)空间复杂度O(1)，时间复杂度O(N). 将新节点先插入至对应原节点的后面，最后将新节点一一拆分出来。

           1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面

           2、遍历链表，A1->random = A->random->next;

           3、将链表拆分成原链表和复制后的链表

 

2)空间复杂度O(N)，时间复杂度O(N).就是使用一个hashmap存储旧节点和对应的新节点，便于后面找随机节点。

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    p := head
    for p != nil {
        newNode := &Node{
            Val:    p.Val,
            Next:   nil,
            Random: nil,
        }
        newNode.Next = p.Next
        p.Next = newNode
        p = p.Next.Next
    }
    p = head
    for p != nil {
        if p.Random != nil {
            p.Next.Random = p.Random.Next
        }
        p = p.Next.Next
    }
    newHead := head.Next
    oldP := head
    p = newHead
    for p.Next != nil {
        oldP.Next = oldP.Next.Next
        p.Next = p.Next.Next
        oldP = oldP.Next
        p = p.Next
    }
    oldP.Next=nil
    return newHead
}

 

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    newHead := Node{
        Val:    head.Val,
        Next:   nil,
        Random: nil,
    }
    p := head.Next
    pre := &newHead
    for p != nil {
        newNode := &Node{
            Val:    p.Val,
            Next:   nil,
            Random: nil,
        }
        pre.Next = newNode
        p = p.Next
        pre = pre.Next
    }
    p = head
    newP := &newHead
    for p != nil {
        if p.Random != nil {
            step := findStep(head, p.Random)
            newP.Random = target(&newHead, step)
        }
        p = p.Next
        newP = newP.Next
    }
    return &newHead
}

//确定从头结点到目标节点所经过的节点数
func findStep(head, target *Node) int {
    p := head
    step := 0
    for p != target {
        p = p.Next
        step++
    }
    return step
}
//返回从头结点开始，走step步所到达的节点
func target(head *Node, step int) *Node {
    p := head
    for step > 0 {
        p = p.Next
        step--
    }
    return p
}