数据结构与算法-链表
目录
25. K 个一组翻转链表 ❤️
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
length++;
}
ListNode dummy = new ListNode(0, head);
ListNode preGroupEnd = dummy;
while (length >= k) {
ListNode cur = preGroupEnd.next;
ListNode groupStart = cur;
ListNode pre = null;
for (int i = 0; i < k; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 原组头反转后变组尾，接下一组起点；上一组尾接新组头。
preGroupEnd.next = pre;
groupStart.next = cur;
preGroupEnd = groupStart;
length -= k;
}
return dummy.next;
}
}
func reverseKGroup(head *ListNode, k int) *ListNode {
length := 0
for cur := head; cur != nil; cur = cur.Next {
length++
}
dummy := &ListNode{Next: head}
preGroupEnd := dummy
for length >= k {
cur := preGroupEnd.Next
groupStart := cur
var pre *ListNode
for i := 0; i < k; i++ {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 原组头反转后变组尾，接下一组起点；上一组尾接新组头。
preGroupEnd.Next = pre
groupStart.Next = cur
preGroupEnd = groupStart
length -= k
}
return dummy.Next
}
92. 反转链表 II
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head);
ListNode preLeft = dummy;
for (int i = 1; i < left; i++) {
preLeft = preLeft.next;
}
ListNode cur = preLeft.next;
ListNode pre = null;
for (int i = left; i <= right; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 原区间头（现在的区间尾）接 right 的后继，前驱接区间新头。
preLeft.next.next = cur;
preLeft.next = pre;
return dummy.next;
}
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummy := &ListNode{Next: head}
preLeft := dummy
for i := 1; i < left; i++ {
preLeft = preLeft.Next
}
cur := preLeft.Next
var pre *ListNode
for i := left; i <= right; i++ {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 原区间头（现在的区间尾）接 right 的后继，前驱接区间新头。
preLeft.Next.Next = cur
preLeft.Next = pre
return dummy.Next
}
23. 合并 K 个升序链表
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int lo, int hi) {
if (lo == hi) {
return lists[lo];
}
int mid = lo + (hi - lo) / 2;
return mergeTwoLists(merge(lists, lo, mid), merge(lists, mid + 1, hi));
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1 {
return lists[0]
}
mid := len(lists) / 2
l1 := mergeKLists(lists[:mid])
l2 := mergeKLists(lists[mid:])
return mergeTwoLists(l1, l2)
}
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
// 剩余的一条整段接上即可。
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
return dummy.Next
}
143. 重排链表 ❤️
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
// 快慢指针找中点，slow 停在前半段末尾。
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode cur = slow.next;
slow.next = null;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode p1 = head, p2 = pre;
while (p2 != null) {
ListNode next1 = p1.next, next2 = p2.next;
p1.next = p2;
p2.next = next1;
p1 = next1;
p2 = next2;
}
}
}
func reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
// 快慢指针找中点，slow 停在前半段末尾。
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
cur := slow.Next
slow.Next = nil
var pre *ListNode
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
p1, p2 := head, pre
for p2 != nil {
next1, next2 := p1.Next, p2.Next
p1.Next = p2
p2.Next = next1
p1 = next1
p2 = next2
}
}
160. 相交链表
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
// 走到尽头就换到另一条链的头，抹平长度差。
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a, b := headA, headB
for a != b {
// 走到尽头就换到另一条链的头，抹平长度差。
if a == nil {
a = headB
} else {
a = a.Next
}
if b == nil {
b = headA
} else {
b = b.Next
}
}
return a
}
82. 删除排序链表中的重复元素 II
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy, cur = head;
while (cur != null) {
boolean isDuplicate = false;
while (cur.next != null && cur.next.val == cur.val) {
cur = cur.next;
isDuplicate = true;
}
if (isDuplicate) {
// 整段重复值一个不留。
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
}
func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre, cur := dummy, head
for cur != nil {
isDuplicate := false
for cur.Next != nil && cur.Next.Val == cur.Val {
cur = cur.Next
isDuplicate = true
}
if isDuplicate {
// 整段重复值一个不留。
pre.Next = cur.Next
} else {
pre = cur
}
cur = cur.Next
}
return dummy.Next
}
148. 排序链表
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 从 dummy 出发找中点，保证两节点时拆成 1 + 1。
ListNode dummy = new ListNode(0, head);
ListNode slow = dummy, fast = dummy;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
slow.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(rightHead);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 从 dummy 出发找中点，保证两节点时拆成 1 + 1。
dummy := &ListNode{Next: head}
slow, fast := dummy, dummy
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
rightHead := slow.Next
slow.Next = nil
l1 := sortList(head)
l2 := sortList(rightHead)
return mergeSorted(l1, l2)
}
func mergeSorted(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
return dummy.Next
}
234. 回文链表
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 反转后半段。
ListNode pre = null, cur = slow;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode left = head, right = pre;
while (right != null) {
if (left.val != right.val) {
return false;
}
left = left.next;
right = right.next;
}
return true;
}
}
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 反转后半段。
var pre *ListNode
cur := slow
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
left, right := head, pre
for right != nil {
if left.Val != right.Val {
return false
}
left = left.Next
right = right.Next
}
return true
}
83. 删除排序链表中的重复元素
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.next.val == cur.val) {
// 跳过重复节点，cur 原地不动继续检查新的后继。
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
func deleteDuplicates(head *ListNode) *ListNode {
cur := head
for cur != nil && cur.Next != nil {
if cur.Next.Val == cur.Val {
// 跳过重复节点，cur 原地不动继续检查新的后继。
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
24. 两两交换链表中的节点 ❤️
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode first = pre.next;
ListNode second = first.next;
// 三步换指针，顺序不能乱。
first.next = second.next;
second.next = first;
pre.next = second;
pre = first;
}
return dummy.next;
}
}
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
pre := dummy
for pre.Next != nil && pre.Next.Next != nil {
first := pre.Next
second := first.Next
// 三步换指针，顺序不能乱。
first.Next = second.Next
second.Next = first
pre.Next = second
pre = first
}
return dummy.Next
}
138. 随机链表的复制
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 第一步：每个原节点后插入拷贝节点。
for (Node cur = head; cur != null; cur = cur.next.next) {
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
// 第二步：拷贝节点的 random 是原 random 的下一个节点。
for (Node cur = head; cur != null; cur = cur.next.next) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
}
// 第三步：拆分两条链，原链要复原。
Node newHead = head.next;
for (Node cur = head; cur != null; cur = cur.next) {
Node copy = cur.next;
cur.next = copy.next;
copy.next = (copy.next != null) ? copy.next.next : null;
}
return newHead;
}
}
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
// 第一步：每个原节点后插入拷贝节点。
for cur := head; cur != nil; cur = cur.Next.Next {
copy := &Node{Val: cur.Val, Next: cur.Next}
cur.Next = copy
}
// 第二步：拷贝节点的 random 是原 random 的下一个节点。
for cur := head; cur != nil; cur = cur.Next.Next {
if cur.Random != nil {
cur.Next.Random = cur.Random.Next
}
}
// 第三步：拆分两条链，原链要复原。
newHead := head.Next
for cur := head; cur != nil; cur = cur.Next {
copy := cur.Next
cur.Next = copy.Next
if copy.Next != nil {
copy.Next = copy.Next.Next
}
}
return newHead
}
61. 旋转链表
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
int length = 1;
ListNode tail = head;
while (tail.next != null) {
length++;
tail = tail.next;
}
k %= length;
if (k == 0) {
return head;
}
// 成环后从原尾走 length - k 步到新尾。
tail.next = head;
for (int i = 0; i < length - k; i++) {
tail = tail.next;
}
ListNode newHead = tail.next;
tail.next = null;
return newHead;
}
}
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
length := 1
tail := head
for tail.Next != nil {
length++
tail = tail.Next
}
k %= length
if k == 0 {
return head
}
// 成环后从原尾走 length - k 步到新尾。
tail.Next = head
for i := 0; i < length-k; i++ {
tail = tail.Next
}
newHead := tail.Next
tail.Next = nil
return newHead
}
补充题 1. 排序奇升偶降链表
class Solution {
public ListNode sortOddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 拆成奇偶两条链。
ListNode odd = head, even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
odd.next = null; // 断尾，防止成环。
// 反转偶数链，使其升序。
ListNode pre = null, cur = evenHead;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 合并两个有序链表。
ListNode dummy = new ListNode();
ListNode tail = dummy;
ListNode l1 = head, l2 = pre;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func sortOddEvenList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 拆成奇偶两条链。
odd, even := head, head.Next
evenHead := even
for even != nil && even.Next != nil {
odd.Next = odd.Next.Next
odd = odd.Next
even.Next = even.Next.Next
even = even.Next
}
odd.Next = nil // 断尾，防止成环。
// 反转偶数链，使其升序。
var pre *ListNode
cur := evenHead
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 合并两个有序链表。
dummy := &ListNode{}
tail := dummy
l1, l2 := head, pre
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
tail.Next = l1
l1 = l1.Next
} else {
tail.Next = l2
l2 = l2.Next
}
tail = tail.Next
}
if l1 != nil {
tail.Next = l1
} else {
tail.Next = l2
}
return dummy.Next
}
86. 分隔链表
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallDummy = new ListNode();
ListNode largeDummy = new ListNode();
ListNode small = smallDummy, large = largeDummy;
for (ListNode cur = head; cur != null; cur = cur.next) {
if (cur.val < x) {
small.next = cur;
small = small.next;
} else {
large.next = cur;
large = large.next;
}
}
large.next = null; // 断尾，防止成环。
small.next = largeDummy.next;
return smallDummy.next;
}
}
func partition(head *ListNode, x int) *ListNode {
smallDummy := &ListNode{}
largeDummy := &ListNode{}
small, large := smallDummy, largeDummy
for cur := head; cur != nil; cur = cur.Next {
if cur.Val < x {
small.Next = cur
small = small.Next
} else {
large.Next = cur
large = large.Next
}
}
large.Next = nil // 断尾，防止成环。
small.Next = largeDummy.Next
return smallDummy.Next
}
109. 有序链表转换二叉搜索树
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
ListNode mid = findMiddle(head);
TreeNode root = new TreeNode(mid.val);
if (head == mid) {
return root; // 只剩一个节点，避免死递归。
}
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
private ListNode findMiddle(ListNode head) {
ListNode pre = null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if (pre != null) {
pre.next = null; // 从中点前切断。
}
return slow;
}
}
func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
mid := findMiddle(head)
root := &TreeNode{Val: mid.Val}
if head == mid {
return root // 只剩一个节点，避免死递归。
}
root.Left = sortedListToBST(head)
root.Right = sortedListToBST(mid.Next)
return root
}
func findMiddle(head *ListNode) *ListNode {
var pre *ListNode
slow, fast := head, head
for fast != nil && fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next.Next
}
if pre != nil {
pre.Next = nil // 从中点前切断。
}
return slow
}
1171. 从链表中删去总和值为零的连续节点
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0, head);
Map<Integer, ListNode> lastSeen = new HashMap<>();
int prefixSum = 0;
for (ListNode cur = dummy; cur != null; cur = cur.next) {
prefixSum += cur.val;
lastSeen.put(prefixSum, cur); // 记录前缀和最后出现的节点。
}
prefixSum = 0;
for (ListNode cur = dummy; cur != null; cur = cur.next) {
prefixSum += cur.val;
cur.next = lastSeen.get(prefixSum).next;
}
return dummy.next;
}
}
func removeZeroSumSublists(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
lastSeen := make(map[int]*ListNode)
prefixSum := 0
for cur := dummy; cur != nil; cur = cur.Next {
prefixSum += cur.Val
lastSeen[prefixSum] = cur // 记录前缀和最后出现的节点。
}
prefixSum = 0
for cur := dummy; cur != nil; cur = cur.Next {
prefixSum += cur.Val
cur.Next = lastSeen[prefixSum].Next
}
return dummy.Next
}
147. 对链表进行插入排序
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode();
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next; // 先存后继，插入会改掉它。
ListNode pre = dummy;
while (pre.next != null && pre.next.val < cur.val) {
pre = pre.next;
}
cur.next = pre.next;
pre.next = cur;
cur = next;
}
return dummy.next;
}
}
func insertionSortList(head *ListNode) *ListNode {
dummy := &ListNode{}
cur := head
for cur != nil {
next := cur.Next // 先存后继，插入会改掉它。
pre := dummy
for pre.Next != nil && pre.Next.Val < cur.Val {
pre = pre.Next
}
cur.Next = pre.Next
pre.Next = cur
cur = next
}
return dummy.Next
}
369. 给单链表加一
class Solution {
public ListNode plusOne(ListNode head) {
Deque<Integer> stack = new ArrayDeque<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
stack.push(cur.val);
}
int carry = 1;
ListNode newHead = null;
while (!stack.isEmpty() || carry > 0) {
int sum = carry + (stack.isEmpty() ? 0 : stack.pop());
carry = sum / 10;
// 头插法：低位先建，挂在结果链前面。
newHead = new ListNode(sum % 10, newHead);
}
return newHead;
}
}
func plusOne(head *ListNode) *ListNode {
var stack []int
for cur := head; cur != nil; cur = cur.Next {
stack = append(stack, cur.Val)
}
carry := 1
var newHead *ListNode
for len(stack) > 0 || carry > 0 {
sum := carry
if len(stack) > 0 {
sum += stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
carry = sum / 10
// 头插法：低位先建，挂在结果链前面。
newHead = &ListNode{Val: sum % 10, Next: newHead}
}
return newHead
}
1669. 合并两个链表
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode dummy = new ListNode(0, list1);
ListNode preA = dummy, afterB = dummy;
for (int i = 0; i < a; i++) {
preA = preA.next;
}
for (int i = 0; i < b + 2; i++) {
afterB = afterB.next;
}
preA.next = list2;
ListNode tail = list2;
while (tail.next != null) {
tail = tail.next;
}
tail.next = afterB;
return dummy.next;
}
}
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
dummy := &ListNode{Next: list1}
preA, afterB := dummy, dummy
for i := 0; i < a; i++ {
preA = preA.Next
}
for i := 0; i < b+2; i++ {
afterB = afterB.Next
}
preA.Next = list2
tail := list2
for tail.Next != nil {
tail = tail.Next
}
tail.Next = afterB
return dummy.Next
}
面试题 02.01. 移除重复节点
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
if (head == null) {
return null;
}
Set<Integer> seen = new HashSet<>();
seen.add(head.val);
ListNode pre = head;
while (pre.next != null) {
if (seen.add(pre.next.val)) {
pre = pre.next;
} else {
// 值已出现，删掉后继节点。
pre.next = pre.next.next;
}
}
return head;
}
}
func removeDuplicateNodes(head *ListNode) *ListNode {
if head == nil {
return nil
}
seen := map[int]bool{head.Val: true}
pre := head
for pre.Next != nil {
if seen[pre.Next.Val] {
// 值已出现，删掉后继节点。
pre.Next = pre.Next.Next
} else {
seen[pre.Next.Val] = true
pre = pre.Next
}
}
return head
}
1367. 二叉树中的链表
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (root == null) {
return false;
}
// 以 root 为起点匹配，或换到左右子树找新起点。
return dfs(root, head) || isSubPath(head, root.left) || isSubPath(head, root.right);
}
private boolean dfs(TreeNode node, ListNode cur) {
if (cur == null) {
return true;
}
if (node == null || node.val != cur.val) {
return false;
}
return dfs(node.left, cur.next) || dfs(node.right, cur.next);
}
}
func isSubPath(head *ListNode, root *TreeNode) bool {
if root == nil {
return false
}
var dfs func(node *TreeNode, cur *ListNode) bool
dfs = func(node *TreeNode, cur *ListNode) bool {
if cur == nil {
return true
}
if node == nil || node.Val != cur.Val {
return false
}
return dfs(node.Left, cur.Next) || dfs(node.Right, cur.Next)
}
// 以 root 为起点匹配，或换到左右子树找新起点。
return dfs(root, head) || isSubPath(head, root.Left) || isSubPath(head, root.Right)
}
1019. 链表中的下一个更大节点
class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> nums = new ArrayList<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
nums.add(cur.val);
}
int[] res = new int[nums.size()];
Deque<Integer> stack = new ArrayDeque<>(); // 单调递减栈，存下标。
for (int i = 0; i < nums.size(); i++) {
while (!stack.isEmpty() && nums.get(i) > nums.get(stack.peek())) {
res[stack.pop()] = nums.get(i);
}
stack.push(i);
}
return res;
}
}
func nextLargerNodes(head *ListNode) []int {
var nums []int
for cur := head; cur != nil; cur = cur.Next {
nums = append(nums, cur.Val)
}
res := make([]int, len(nums))
var stack []int // 单调递减栈，存下标。
for i, num := range nums {
for len(stack) > 0 && num > nums[stack[len(stack)-1]] {
res[stack[len(stack)-1]] = num
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return res
}
725. 分隔链表
class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
int length = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
length++;
}
int partSize = length / k;
int extra = length % k; // 前 extra 段各多一个节点。
ListNode[] res = new ListNode[k];
ListNode cur = head;
for (int i = 0; i < k && cur != null; i++) {
res[i] = cur;
int size = partSize + (i < extra ? 1 : 0);
for (int j = 1; j < size; j++) {
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return res;
}
}
func splitListToParts(head *ListNode, k int) []*ListNode {
length := 0
for cur := head; cur != nil; cur = cur.Next {
length++
}
partSize := length / k
extra := length % k // 前 extra 段各多一个节点。
res := make([]*ListNode, k)
cur := head
for i := 0; i < k && cur != nil; i++ {
res[i] = cur
size := partSize
if i < extra {
size++
}
for j := 1; j < size; j++ {
cur = cur.Next
}
next := cur.Next
cur.Next = nil
cur = next
}
return res
}
146. LRU 缓存
class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node() {}
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> cache = new HashMap<>();
private final Node head = new Node(); // 头尾哨兵，免去判空。
private final Node tail = new Node();
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
if (cache.size() > capacity) {
Node removed = removeTail();
cache.remove(removed.key);
}
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private Node removeTail() {
Node node = tail.prev;
removeNode(node);
return node;
}
}
type Node struct {
key, value int
prev, next *Node
}
type LRUCache struct {
capacity int
cache map[int]*Node
head, tail *Node // 头尾哨兵，免去判空。
}
func Constructor(capacity int) LRUCache {
head, tail := &Node{}, &Node{}
head.next = tail
tail.prev = head
return LRUCache{
capacity: capacity,
cache: make(map[int]*Node),
head: head,
tail: tail,
}
}
func (c *LRUCache) Get(key int) int {
node, ok := c.cache[key]
if !ok {
return -1
}
c.moveToHead(node)
return node.value
}
func (c *LRUCache) Put(key int, value int) {
if node, ok := c.cache[key]; ok {
node.value = value
c.moveToHead(node)
return
}
newNode := &Node{key: key, value: value}
c.cache[key] = newNode
c.addToHead(newNode)
if len(c.cache) > c.capacity {
removed := c.removeTail()
delete(c.cache, removed.key)
}
}
func (c *LRUCache) moveToHead(node *Node) {
c.removeNode(node)
c.addToHead(node)
}
func (c *LRUCache) addToHead(node *Node) {
node.prev = c.head
node.next = c.head.next
c.head.next.prev = node
c.head.next = node
}
func (c *LRUCache) removeNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (c *LRUCache) removeTail() *Node {
node := c.tail.prev
c.removeNode(node)
return node
}