1. 下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
出处：
https://edu.csdn.net/practice/27361970
代码：
import java.util.*; public class Solution3 { public static void nextPermutation(int[] nums) { int i = nums.length - 1; while (i > 0 && nums[i] <= nums[i - 1]) { i--; } if (i > 0) { int j = nums.length - 1; while (j >= 0 && nums[j] <= nums[i - 1]) { j--; } swap(nums, i - 1, j); } reverse(nums, i); } private static void reverse(int[] nums, int i) { int j = nums.length - 1; while (i < j) { swap(nums, i, j); i++; j--; } } private static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public static void main(String[] args) { int[] nums1 = {1,2,3}; int[] nums2 = {3,2,1}; int[] nums3 = {1,1,5}; System.out.println(Arrays.toString(nums1)); nextPermutation(nums1); System.out.println(Arrays.toString(nums1)); System.out.println(Arrays.toString(nums2)); nextPermutation(nums2); System.out.println(Arrays.toString(nums2)); System.out.println(Arrays.toString(nums3)); nextPermutation(nums3); System.out.println(Arrays.toString(nums3)); } }
输出：
[1, 2, 3]
[1, 3, 2]
[3, 2, 1]
[1, 2, 3]
[1, 1, 5]
[1, 5, 1]
2. 分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
出处：
https://edu.csdn.net/practice/27361971
代码：
import java.util.*; public public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } class Solution { public ListNode partition(ListNode head, int x) { ListNode dummyHead1 = new ListNode(0); ListNode dummyHead2 = new ListNode(0); ListNode node1 = dummyHead1; ListNode node2 = dummyHead2; while (head != null) { if (head.val < x) { node1.next = head; head = head.next; node1 = node1.next; node1.next = null; } else { node2.next = head; head = head.next; node2 = node2.next; node2.next = null; } } node1.next = dummyHead2.next; return dummyHead1.next; } public static void main(String[] args) { } }
输出：
3. 复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val,random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
0 <= n <= 1000
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
出处：
https://edu.csdn.net/practice/27361972
代码：
class Node { public int val; public Node left; public Node right; public Node next; public Node() { } public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; class Solution { public Node copyRandomList(Node head) { if (head == null) return null; Map<Node, Node> map = new HashMap(); Node p = head; while (p != null) { map.put(p, new Node(p.val)); p = p.next; } p = head; while (p != null) { map.get(p).next = map.get(p.next); map.get(p).random = map.get(p.random); p = p.next; } return map.get(head); } }
输出：
