位元組跳動企業題庫，連結清單系列，因為有leetcode會員能看到企業出題頻率，那我們從出題頻率最高刷到最低，題目有21. 合并兩個有序連結清單 、146. LRU緩存機制、92. 反轉連結清單II
21. 合并兩個有序連結清單
【簡單】【題目描述】将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。
示例 1：輸入：l1 = [1,2,4], l2 = [1,3,4] 輸出：[1,1,2,3,4,4]
示例 2：輸入：l1 = [], l2 = [] 輸出：[]
示例 3：輸入：l1 = [], l2 = [0] 輸出：[0]
這道題是一到老生常談的題目，對于熟悉連結清單的同學來說是秒殺的，我們分遞歸和疊代兩種方法解題
【疊代、遞歸】圖解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/* 遞歸法：O(m+n)，空間複雜度O(m+n) */
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 如果兩個連結清單有一個為空，遞歸結束。
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
// 判斷 l1 和 l2 哪一個連結清單的頭節點的值更小，然後遞歸地決定下一個添加到結果裡的節點。
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
} 23. 合并K個有序連結清單
【困難】【題目描述】給你一個連結清單數組，每個連結清單都已經按升序排列。請你将所有連結清單合并到一個升序連結清單中，傳回合并後的連結清單。
示例 1：輸入：lists = [[1,4,5],[1,3,4],[2,6]] 輸出：[1,1,2,3,4,4,5,6]
解釋：連結清單數組如下：
[
1->4->5,
1->3->4,
2->6
]
将它們合并到一個有序連結清單中得到。
1->1->2->3->4->4->5->6
示例 2：輸入：lists = [[]] 輸出：[]
【暴力、遞歸、疊代】圖解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/*K 指針：K 個指針分别指向K條連結清單;每次O(K)比較K個指針min, 時間複雜度O(NK)*/
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
while (true) {
ListNode minNode = null;
int minPointer = -1;
for (int i = 0; i < k; i++) {
if (lists[i] == null) {
continue;
}
if (minNode == null || lists[i].val < minNode.val) {
minNode = lists[i];
minPointer = i;
}
}
if (minPointer == -1) {
break;
}
tail.next = minNode;
tail = tail.next;
lists[minPointer] = lists[minPointer].next;
}
return dummyHead.next;
}
} class Solution {
/*兩兩合并 - 疊代*/
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
int k = lists.length;
while (k > 1) {
int idx = 0;
for (int i = 0; i < k; i += 2) {
if (i == k - 1) {
lists[idx++] = lists[i];
} else {
lists[idx++] = merge2Lists(lists[i], lists[i + 1]);
}
}
k = idx;
}
return lists[0];
}
}
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;
ListNode l1 = merge(lists, lo, mid);
ListNode l2 = merge(lists, mid + 1, hi);
return merge2Lists(l1, l2);
}
} 146. LRU緩存機制
【中等】【題目描述】運用你所掌握的資料結構，設計和實作一個LRU(最近最少使用) 緩存機制
實作 LRUCache 類：
LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關鍵字 key 存在于緩存中，則傳回關鍵字的值，否則傳回 -1 。
void put(int key, int value) 如果關鍵字已經存在，則變更其資料值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新資料之前删除最久未使用的資料值，進而為新的資料值留出空間。
進階：你是否可以在 O(1) 時間複雜度内完成這兩種操作？
示例：輸入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出：[null, null, null, 1, null, -1, null, -1, 3, 4]
解釋：
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1); // 傳回 1
lRUCache.put(3, 3); // 該操作會使得關鍵字 2 廢棄，緩存是 {1=1, 3=3}
lRUCache.get(2); // 傳回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關鍵字 1 廢棄，緩存是 {4=4, 3=3}
lRUCache.get(1); // 傳回 -1 (未找到)
lRUCache.get(3); // 傳回 3
lRUCache.get(4); // 傳回 4
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用僞頭部和僞尾部節點
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通過哈希表定位，再移到頭部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，建立一個新的節點
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加進哈希表
cache.put(key, newNode);
// 添加至雙向連結清單的頭部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除雙向連結清單的尾部節點
DLinkedNode tail = removeTail();
// 删除哈希表中對應的項
cache.remove(tail.key);
--size;
}
}
else {
// 如果 key 存在，先通過哈希表定位，再修改 value，并移到頭部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/