剑指 Offer 35.复杂链表的复制

题目描述

原题
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例 1:
img
1
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
2
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
Copied!
示例 2:
img
1
输入:head = [[1,1],[2,1]]
2
输出:[[1,1],[2,1]]
Copied!
示例 3:
img
1
输入:head = [[3,null],[3,0],[3,null]]
2
输出:[[3,null],[3,0],[3,null]]
Copied!
示例 4:
1
输入:head = []
2
输出:[]
3
解释:给定的链表为空(空指针),因此返回 null。
Copied!
提示:
    -10000 <= Node.val <= 10000
    Node.random 为空(null)或指向链表中的节点。
    节点数目不超过 1000 。
注意:本题与主站 138 题相同:https://leetcode-cn.com/problems/copy-list-with-random-pointer/

题解

1
/*
2
// Definition for a Node.
3
class Node {
4
int val;
5
Node next;
6
Node random;
7
8
public Node(int val) {
9
this.val = val;
10
this.next = null;
11
this.random = null;
12
}
13
}
14
*/
15
class Solution {
16
public Node copyRandomList(Node head) {
17
if(head==null) return null;
18
Node cur = head;
19
//1. 复制节点
20
while(cur!=null){
21
Node tmp = new Node(cur.val);
22
tmp.next = cur.next;
23
cur.next = tmp;
24
cur = tmp.next;
25
}
26
cur = head;
27
while(cur!=null){
28
//指向复制出来的random 所以是cur.random.next
29
if(cur.random!=null)
30
cur.next.random = cur.random.next;
31
cur = cur.next.next;
32
}
33
cur = head.next;
34
Node res = cur;
35
Node pre = head;
36
while(cur.next!=null){
37
pre.next = pre.next.next;
38
cur.next = cur.next.next;
39
pre = pre.next;
40
cur = cur.next;
41
}
42
pre.next = null;
43
//拆分两个链表
44
return res;
45
}
46
}
Copied!
最近更新 9mo ago
复制链接