707. 设计链表
设计链表的实现，您可以选择使用单链表或双链表。
在链表类中实现这些功能：
get(index)：获取链表中第index个节点的值。如果索引无效，则返回1。addAtHead(val)：在链表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。addAtTail(val)：将值为val的节点追加到链表的最后一个元素。addAtIndex(index,val)：在链表中的第index个节点之前添加值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。deleteAtIndex(index)：如果索引index有效，则删除链表中的第index个节点。
使用单链表
第一个黄色的结点是哨兵结点，由于它的存在，链表永远不会为空。它不存储实际的值，作用是方便对头结点的插入和删除。
addAtIndex 、addAtHead 、addAtTail ：因为哨兵结点的存在，addAtHead、addAtTail 可以用 addAtIndex 来实现。
要在指定位置插入结点，需要先找到这个位置的前驱结点，然后修改相关 next 指针即可。
class ListNode {
int val;
ListNode next;
public ListNode(int val) { this.val = val; }
}
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
this.size = 0;
this.head = new ListNode(0);
}
public int get(int index) {
if (index < 0 || index >= size) return -1;
ListNode node = head;
for (int i = 0; i <= index; i++) node = node.next;
return node.val;
}
public void addAtIndex(int index) {
if (index > size) return;
if (index < 0) index = 0;
ListNode newNode = new ListNode(val);
ListNode pre = head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
newNode.next = pre.next;
pre.next = newNode;
this.size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
ListNode pre = head;
for (int i = 0; i < index; i++) pre = pre.next;
pre.next = pre.next.next;
this.size--;
}
}
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
方法一：递归
递归的三要素：
- 递归的终止条件：递归到链表为空，或者只剩下一个结点时，递归终止。
- 返回给上一层递归的值：已经交换过的子链表。
- 本级递归的任务：假设待交换的两个结点为
head和next，当前递归的任务就是交换这两个结点。
public ListNode swapPairs(ListNode head) {
// 终止条件
if (head == null || head.next == null) return head;
// 当前层的任务
ListNode next = head.next;
ListNode completed = swapPairs(next.next);
head.next = completed;
next.next = head;
// 返回给上一层的值
return next;
}
方法二：迭代（模拟）
创建指向头结点的哑结点 dummy ，用 temp 表示当前到达的结点，初始时 temp 指向 dummy 。每次需要交换 temp 后面的两个结点。
- 如果后面不够两个结点，则结束。
- 获得后面的两个结点
node1和node2，更新指针关系。 - 然后让
temp指向node1，继续迭代。 - 最后返回新的头结点
dummy.next。
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode temp = dummy;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = node1.next;
ListNode node3 = node2.next;
temp.next = node2;
node2.next = node1;
node1.next = node3;
temp = node1;
}
return dummy.next;
}
206. 反转链表
方法一：迭代
迭代过程容易理解，每次将一个箭头反向，同时滚动向后即可。
ListNode reverseList(ListNode head) {
if(head == null || head.next = null) return head;
ListNode pre = null, cur = head;
while(cur != null) {
ListNode next = cur.next; // 先缓存 next
cur.next = pre; // 箭头反向
pre = cur; // 向后滚动
cur = next;
}
return pre; // 最后 cur == null
}
方法二：递归
递归过程有些绕，在当前层，可以将后面的部分当做已经反转过的，只需将当前结点的 next 箭头反向。
ListNode reverseList(ListNode head) {
// 递归出口(在递归的最深层，head 会指向最后一个结点，直接将它返回，并作为结果头结点)
if(head == null || head.next == null) return head;
ListNode returnNode = reverseList(head.next);
// 反转当前箭头
head.next.next = head;
head.next = null;
return returnNode;
}
19. 删除链表的倒数第 N 个结点
分析：由于可能会删除头结点，所以设置哑结点会方便很多，这样不必对头结点进行特殊的判断。这个问题可以有很多种解法。
方法一：计算链表长度。首先遍历一遍链表，获取长度 L，然后将哑结点作为第一个结点，那么第 L-n+1 个结点就是待删除的目标结点，我们获取其前驱结点（第 L-n 个结点）即可。时间复杂度 \(O(L)\)，空间复杂度 \(O(1)\)。
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
int L = getLength(head);
ListNode p = dummy;
for(int i = 0; i < L-n; i++)
p = p.next;
// 此时 p 为待删除结点的前驱
p.next = p.next.next;
return dummy.next;
}
方法二：借助栈。用一个栈存储所有结点，然后依次弹出栈顶结点，弹出的第 n 个就是待删除结点，获取弹出的第 n+1 个结点即可执行删除操作。时间复杂度 \(O(L)\)，空间复杂度 \(O(L)\)。
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
Deque<ListNode> stack = new LinkedList<>();
ListNode p = dummy;
while(p != null){
stack.push(p);
p = p.next;
}
for(int i = 0; i < n; i++)
stack.pop();
ListNode pre = stack.pop();
pre.next = pre.next.next;
return dummy.next;
}
方法三：双指针。初始时， slow 指针指向哑结点， fast 指针指向第 n+1 个结点。然后同步移动，直到 fast 指向 null 。这时 slow 指向的就是待删除结点的前驱结点。时间复杂度 \(O(L)\)，空间复杂度 \(O(1)\)。
234. 回文链表
判断给定链表是否为回文链表，即从前往后和从后往前遍历结果一样。
借助栈来逆序存储每个结点，然后逐一出栈和原链表结点比较，比较容易理解。但还可以优化到常数的空间复杂度——将前半部分/后半部分链表反转，然后和另外一部分比较。
boolean isPalindrome(ListNode head) {
ListNode headOfSecondHalf = findStartOfSecondHalf(head);
ListNode p1 = head, p2 = invertList(headOfSecondHalf);
while(p2 != null) {
if(p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}
// 使用双指针找到后半部分的第一个结点
// 1 -> 2
// 1 -> 2 -> 3
// 1 -> 2 -> 3 ->4
ListNode findStartOfSecondHalf(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
// 反转链表，可以用迭代/递归两种方法
ListNode inverteList(ListNode head) {
if(head == null || head.next == null)
return head;
// 先递归反转后边的列表
ListNode returnedNode = inverteList(head.next);
// 再反转当前节点
head.next.next = head;
head.next = null;
return returnedNode;
}
21. 合并两个有序链表
将两个有序链表就地合并，返回合并后的链表。
分析：可以用递归或者迭代来做。
递归：可以递归地定义两个链表的合并操作，如下：
\[\begin{cases} \text {list1}[0]+\text {merge}(\text {list1}[1:], \text {list2} )， & \text {list1}[0]<\text {list2}[0] \\ \text {list2}[0]+\text {merge}(\text {list1}, \text {list2}[1:]) ，& \text {otherwise} \end{cases} \]我们直接将以上递归过程建模，同时考虑边界情况（链表是否为空）即可。
ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
else if (l2 == null) return l1;
else if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l2.next, l1);
return l2;
}
}
递归方法的时间和空间复杂度都为 \(O(n+m)\)。
迭代：当两表都不为空时，不断比较两表头部结点的大小，将较小的连入结果链表，同时将指向该链表的指针后移一位。具体来说，
- 需要设置一个哨兵结点，以便最后结果的返回。
- 同时维护一个
pre指针，用来记录结果链表在上一轮迭代后的尾结点，用来将当前迭代的较小结点连入结果链表。 - 迭代结束时，至多有一个链表非空，将其连入结果链表即可。
ListNode merge(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1); // 哨兵结点
ListNode pre = prehead;
while(l1 != null && l2 != null) {
if (l1.val < l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
pre.next = (l1 != null) ? l1 : l2;
return prehead.next;
}
迭代方法的时间复杂度仍为 \(O(n+m)\)，而空间复杂度仅为 \(O(1)\)。
83. 删除排序链表中的重复元素
将 1->1->2 变成 1->2 。
类似于排序树组的元素去重，使用快慢指针，快指针探测新元素，慢指针记录不重复的元素。
ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode fast = head, slow = head;
while (fast != null) {
if (fast.val != slow.val) {
slow.next = fast;
slow = slow.next;
}
fast = fast.next;
}
slow.next = null; // 断开与后面的连接
return head;
}
82. 删除排序链表中的重复元素 II
将 1->2->2->3 变成 1->3 。
不同于保留一个重复结点，删除所有重复结点需要增加一个内层循环，用来不断删除重复出现的结点。具体来说，如果探测到重复结点，则记下这个重复的值 x，同时删除第一个重复结点，而后不断删除值为 x 的结点。
ListNode deleteDuplicates(ListNode head) {
if(head == null) return null;
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy, cur = head;
while(cur != null && cur.next != null) {
// 探测是否出现重复结点
if(cur.val == cur.next.val) {
int x = cur.val;
while(cur != null && cur.val == x) {
cur = cur.next;
}
pre.next = cur;
} else {
pre = pre.next;
cur = cur.next;
}
}
}
146. LRU 缓存
设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
LRUCache(int capacity)以 正整数 作为容量 capacity 初始化 LRU 缓存。int get(int key)如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value)如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
实现本题的两种操作，需要用到一个哈希表和一个双向链表。在面试中，面试官一般会期望读者能够自己实现一个简单的双向链表 来维护所有在缓存中的键值对，而不是使用语言自带的、封装好的数据结构。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表即为普通的哈希映射，通过缓存数据的键映射到其在双向链表中的位置。
这样一来，在访问一个元素时，首先使用哈希表进行定位，找出缓存项在双向链表中的位置，然后将其移动到链表头部。具体方法如下：
- 对于
get操作，首先判断key是否存在：- 如果不存在，返回 -1；
- 如果存在，则通过哈希表定位
key的位置，将其移动到链表头部，最后返回其value。
- 对于
put操作，首先判断key是否存在：- 如果不存在，则创建该结点，并将其添加到链表头部，同时将其映射到哈希表。然后判断链表的结点数是否超出容量，超出则删除链表的尾部节点，并删除哈希表中对应的项。
- 如果存在，则先通过哈希表定位，然后更新对应结点，最后将其移动到链表头部。
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private int size;
private int capacity;
private DLinkedNode head;
private DLinkedNode tail;
private HashMap<Integer, DLinkedNode> cache = new HashMap<>();
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;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node != null) {
// 结点存在，则更新其值，并移动到链表头部
node.value = value;
moveToHead(node);
} else {
// 不存在，则创建并添加到链表头部，如果超出容量，则移除尾部节点
DLinkedNode newNode = new DLinkedNode(key, value);
addToHead(newNode);
cache.put(key, newNode);
size++;
if(size > capacity) {
cache.remove(tail.prev.key);
removeNode(tail.prev);
size--;
}
}
}
private void addToHead(DLinkedNode node) {
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
}