扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 面试宝典系列

    • 剑指 Offer 题解
  • 数组与矩阵

  • 栈队列堆

  • 双指针

  • 链表

    • 6. 从尾到头打印链表
    • 18 删除链表节点
    • 22. 链表中倒数第 K 个结点
    • 23. 链表中环的入口结点
    • 24. 反转链表
    • 25. 合并两个排序的链表
    • 35. 复杂链表的复制
    • 52. 两个链表的第一个公共结点
  • 树

  • 贪心思想

  • 二分查找

  • 分治

  • 搜索

  • 排序

  • 动态规划

  • 数学

  • 位运算

  • 其他

扫码订阅《 》或入驻星球,即可阅读文章!

35. 复杂链表的复制


GOLANG ROADMAP

# 题目链接

牛客 (opens new window)

力扣 (opens new window)

# 题目描述

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

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

    RandomListNode(int label) {
        this.label = label;
    }
}
1
2
3
4
5
6
7
8
9

# 解题思路

# 方法一

第一次遍历原链表时不考虑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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

这种方法时间复杂度为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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

时间复杂度为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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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

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

  • 题目链接
  • 题目描述
  • 解题思路
  • 方法一
  • 方法二
  • 方法三