关键词：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
中等难度的题目。要求对这个链表进行深拷贝，返回深拷贝后的链表头节点。
可以使用HashMap存储新旧节点的映射关系，然后再依次设置引用关系即可，这种方法最简单：
/**
* 使用hashmap存储对应的关系
* 空间复杂度O(n)
*/
public Node copyRandomList(Node head)
if (head == null)
return head;
Node node = head;
/*
* 使用hash表存储旧结点和新结点的映射关系
*/
Map<Node, Node> map = new HashMap<>();
while (node != null)
//新建节点，只填充值
Node clone = new Node(node.val);
map.put(node, clone);
node = node.next;
/*
* 进行引用的映射关联
*/
node = head;
while (node != null)
//新节点的next
map.get(node).next = map.get(node.next);
//新节点的random
map.get(node).random = map.get(node.random);
node = node.next;
return map.get(head);
上一种方法需要空间复杂度O(n)，因为借助了辅助结构，另一种方法是，新建克隆节点，然后放在原节点后面，然后调整复制节点的random指向，然后再分离新旧节点返回新节点组成的链表。这种方法的时间复杂度为O(1)。
/**
* 不使用其它数据结构，将新的节点放在原节点后面，然后再分离
* 空间复杂度O(1)
*/
public Node copyRandomList(Node head)
if (head == null)
return head;
Node node = head;
//新建节点放在复制的节点后面
while (node != null)
Node newNode = new Node(node.val);
newNode.next = node.next;
node.next = newNode;
node = newNode.next;
node = head;
//调整复制的节点的random的指向
while (node != null)
node.next.random = (node.random != null) ? node.random.next : null;
node = node.next.next;
node = head;
//调整复制的节点的next的指向，分离链表
Node newHead = head.next;
while (node.next != null)
Node temp = node.next;
node.next = node.next.next;
node = temp;
return newHead;
leetcodejava刷题笔记—394.字符串解码
133.克隆图给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。中等难度。使用DFS深度优先遍历即可解决。publicNodecloneGraph(Nodenode)if(node==null)returnnode;//hashmap存储新旧节点的对应关系，以及用... 查看详情
leetcodejava刷题笔记—445.两数相加ii
...将这两数相加会返回一个新的链表。中等难度。这道题和LeetCodeJava刷题笔记—2.两数相加是类似的题目，区别就是这道题是顺序存储的，而2.两数相加则是逆序存储的。那么这道题的解法很简单，使用两个栈将l1和l2的... 查看详情
leetcodejava刷题笔记—338.比特位计数
338.比特位计数给你一个整数n，对于0<=i<=n中的每个i，计算其二进制表示中1的个数，返回一个长度为n+1的数组ans作为答案。简单难度。这道题我们可以对每一个数循环进行191.位1的个数的元算即可。publicin... 查看详情
leetcodejava刷题笔记—24.两两交换链表中的节点
...;只能进行节点交换）。中等难度。这道题实际上就是LeetCodeJava刷题笔记—25.K个一组翻转链表的特殊情况，因此我们直接带入即可求解：publicListNo 查看详情
leetcodejava刷题笔记—101.对称二叉树(代码片段)
101.对称二叉树给你一个二叉树的根节点root，检查它是否轴对称。简单难度。这道题与剑指Offer28.对称的二叉树属于同一道题。最好理解的是对位节点进行双递归。publicbooleanisSymmetric(TreeNoderoot)if(root==null)returntrue;//双递... 查看详情
leetcodejava刷题笔记—111.二叉树的最小深度(代码片段)
...点的最短路径上的节点数量。简单难度。这道题看起来和LeetCodeJava刷题笔记—104.二叉树的最大深度是相反的，但是却不能像求最大深度那样使用一行代码解决，因为还要考虑特殊情况，如果左子树为null，则最小... 查看详情
leetcodejava刷题笔记—148.排序链表
148.排序链表在O(nlogn)时间复杂度和常数级空间复杂度下，对链表进行排序。由于需要O(nlogn)时间复杂度，那么肯定就是归并排序、快速排序和堆排序。实际上链表排序大部分都是用归并排序，它是一种稳定的排序。所... 查看详情
leetcodejava刷题笔记—226.翻转二叉树(代码片段)
226.翻转二叉树给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。简单难度。这道题与剑指Offer27.二叉树的镜像属于同一道题。使用后续递归交换左右子节点的位置的方式是最简单的。publicTreeNodeinvertTree(Tre... 查看详情
leetcodejava刷题笔记—328.奇偶链表
328.奇偶链表给定单链表的头节点head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。中等难度... 查看详情
leetcodejava刷题笔记—191.位1的个数
191.位1的个数编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为‘1’的个数（也被称为汉明重量）。简单难度。这里我们借助n&(n-1)的特性，即该运算... 查看详情
leetcodejava刷题笔记—160.相交链表
160.相交链表给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。简单难度，这道题和剑指Offer52.两个链表的第一个公共节点是同一道题。A和B两... 查看详情
leetcodejava刷题笔记—394.字符串解码
394.字符串解码给定一个经过编码的字符串，返回它解码后的字符串。编码规则为:k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数，并且支持嵌套编码。原始数据不包含数字，所... 查看详情
leetcodejava刷题笔记—110.平衡二叉树
110.平衡二叉树给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。说白了就是判断二叉树是不是平衡二叉树。简... 查看详情
leetcodejava刷题笔记—1.两数之和(代码片段)
1.两数之和给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。简单难度。使用一个hashMap记录元素值与索引的对应关系，遍历数组，判断如果... 查看详情
leetcodejava刷题笔记—543.二叉树的直径
543.二叉树的直径给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。两结点之间的路径长度是以它们之间边的数目表示。简单难... 查看详情
leetcodejava刷题笔记—104.二叉树的最大深度
104.二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:叶子节点是指没有子节点的节点。简单难度。这道题很简单，采用分治算法即可。所谓分治&#x... 查看详情
leetcodejava刷题笔记—144.二叉树的前序遍历(代码片段)
144.二叉树的前序遍历给你二叉树的根节点root，返回它节点值的前序遍历。简单难度。先访问根节点，再前序遍历左子树，再前序遍历右子树。最简单的就是使用递归的方式。publicList<Integer>preorderTraversal(TreeNoderoot... 查看详情
leetcodejava刷题笔记—145.二叉树的后序遍历(代码片段)
145.二叉树的后序遍历给你一棵二叉树的根节点root，返回其节点值的后序遍历。简单难度。先后序遍历左子树，再后序遍历右子树，再访问根节点。最简单的就是使用递归的方式。publicList<Integer>postorderTraversal(TreeN... 查看详情