35. 复杂链表的复制

题目链接

牛客

力扣

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。

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

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

解题思路

方法一

第一次遍历原链表时不考虑random指针，只是复制节点； 第二次遍历原链表时只考虑random指针。

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

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
}

这种方法时间复杂度为O(n^2)，主要耗时在于确定新节点的random指针上。

方法二

用空间换时间，使用map数据结构，保存原节点与新节点的对应关系，这样在确定random指针时可快速定位新节点。

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

func copyRandomList(head *Node) *Node {
    if head == nil {
		return nil
	}
	newHead := Node{
		Val:    head.Val,
		Next:   nil,
		Random: nil,
	}
	p := head.Next
	pre := &newHead
	connection := make(map[*Node]*Node)
	connection[head] = pre
	for p != nil {
		newNode := &Node{
			Val:    p.Val,
			Next:   nil,
			Random: nil,
		}
		pre.Next = newNode
		connection[p] = newNode
		p = p.Next
		pre = pre.Next
	}
	p = head
	newP := &newHead
	for p != nil {
		if p.Random != nil {
			newP.Random = connection[p.Random]
		}
		p = p.Next
		newP = newP.Next
	}
	return &newHead
}

时间复杂度为O(n)，空间复杂度为O(n)

方法三

将新节点先插入至对应原节点的后面，最后将新节点一一拆分出来。

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

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
}

注意：最后还需要将原链表复原，否则系统会报"Next pointer of node with label 7 from the original list was modified."这样的错误。

时间复杂度为O(n)，空间复杂度为O(1)