本系列為筆者的 Leetcode 刷題記錄，順序為 Hot 100 題官方順序，根據標簽命名，記錄筆者總結的做題思路，附部分代碼解釋和疑問解答，01~07為C++語言，08及以后為Java語言。

01 合并 K 個升序鏈表

/*** 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 {public ListNode mergeKLists(ListNode[] 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 {public ListNode mergeKLists(ListNode[] lists) {int k = lists.length;ListNode dummy = null;for(int i=0; i<k; i++){dummy = mergeTwoLists(dummy, lists[i]);}return dummy;}//合并兩個有序鏈表public ListNode mergeTwoLists(ListNode l1, ListNode l2){ListNode l3 = new ListNode(0);ListNode flag = l3; //return flag.nextwhile(l1 != null && l2 != null){if(l1.val < l2.val){l3.next = l1;l1 = l1.next;}else{l3.next = l2;l2 = l2.next;}l3 = l3.next;}if(l1 != null){l3.next = l1;}if(l2 != null){l3.next = l2;}return flag.next;}
}

方法二：二分法（遞歸）+ 合并兩個有序鏈表

/*** 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 {public ListNode mergeKLists(ListNode[] lists) {return merge(lists, 0, lists.length-1);}public ListNode merge(ListNode[] lists, int left, int right){if(left == right){return lists[left];}if(left > right){return null; //為啥捏？}int mid = (left + right) / 2;return mergeTwoLists(merge(lists, left, mid), merge(lists, mid+1, right));}//合并兩個有序鏈表public ListNode mergeTwoLists(ListNode l1, ListNode l2){ListNode l3 = new ListNode(0);ListNode flag = l3; //return flag.nextwhile(l1 != null && l2 != null){if(l1.val < l2.val){l3.next = l1;l1 = l1.next;}else{l3.next = l2;l2 = l2.next;}l3 = l3.next;}if(l1 != null){l3.next = l1;}if(l2 != null){l3.next = l2;}return flag.next;}
}

在什么情況下left > right，為什么要返回null值？

當你調用 mergeKLists 時，假設 lists 為空數組，即 lists.length == 0，那么初始調用 merge(lists, 0, -1) 就會發生 left > right 的情況，在這種情況下，返回 null 是合理的，因為沒有鏈表可以合并。

02 LRU 緩存

class LRUCache {public LRUCache(int capacity) {}public int get(int key) {}public void put(int key, int value) {}
}/*** 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);*/

方法：哈希映射 + 雙向鏈表

class LRUCache {//1.自定義雙向鏈表結點class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value){this.key = _key;this.value = _value;}}//2.自定義哈希映射 cache <int, DLinkedNode>private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size, capacity;private DLinkedNode head, tail;/*3.初始化LRU緩存a.初始化 size, capacityb.初始化 head, tail*/public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}/*4.查詢操作：如果key在cache中，返回value；否則，返回-1a. node = null, return -1b. node != null, move to head, return node.value*/public int get(int key) {DLinkedNode node = cache.get(key);if(node == null){return -1;}/*move to heada. remove nodeb. add to head*/node.prev.next = node.next;node.next.prev = node.prev;node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;return node.value;}/*5.更新操作：如果key在cache中，更新value；否則，插入cache <key, nodeNew>a. node = nulli.創建 nodeNewii.插入 cache <key, nodeNew>, add to headiii. size > capacity, remove tailb. node != null, move to head*/public void put(int key, int value) {DLinkedNode node = cache.get(key);if(node == null){DLinkedNode nodeNew = new DLinkedNode(key, value);cache.put(key, nodeNew);++size;// add to headnodeNew.prev = head;nodeNew.next = head.next;head.next.prev = nodeNew;head.next = nodeNew;if(size > capacity){DLinkedNode res = tail.prev;//remove noderes.prev.next = res.next;res.next.prev = res.prev;cache.remove(res.key);--size;}}else{node.value = value;/*move to heada. remove nodeb. add to head*/node.prev.next = node.next;node.next.prev = node.prev;node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}}
}/*** 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);*/

① 為什么要采用雙向鏈表，而不是單向鏈表？

• 快速刪除：雙向鏈表可以從鏈表中的任何位置快速移除節點，因為每個節點都有一個指向前驅節點的指針，而單向鏈表則需要從頭開始遍歷才能找到前驅節點。
• 移動節點到頭部：在LRU緩存中，頻繁的操作是將節點移動到鏈表頭部。如果采用單向鏈表，這個操作會更復雜且效率低下，而雙向鏈表可以在常數時間內完成。

② 為什么要將DLinkedNode定義為內部類？

• 封裝：DLinkedNode僅在LRUCache中使用，將其作為內部類可以更好地實現封裝。
• 簡化代碼：在內部類中可以直接訪問外部類的私有成員和方法，簡化了代碼的結構，而無需額外的getter/setter。
• 邏輯關系清晰：DLinkedNode本質上是LRUCache的一部分，通過內部類的方式可以更明確地表達這種包含關系。