160. 相交链表
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。
图示两个链表在节点 c1 开始相交：
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
具体题解
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while (A != B) {
if (A != null) {
A = A.next;
} else {
A = headB;
}
if (B != null) {
B = B.next;
} else {
B = headA;
}
}
return A;
}
}
思路解析
假设有交点的话，A 长度 + B 部分长度 = B 长度 + A 部分长度。最终 A 与 B 一定会相同，可能是 null 也可能是共同节点。
必会知识
无
206. 反转链表
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
具体题解
class Solution {
public ListNode reverseList(ListNode head) {
return recur(head, null);
}
public ListNode recur(ListNode cur, ListNode pre) {
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
思路解析
着眼于当前节点与上一节点。调整当前节点指向上一节点，再重新换 cur 与 pre 进行下一轮。
必会知识
无
234. 回文链表
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
具体题解
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<>();
ListNode tmp = head;
while (tmp != null) {
vals.add(tmp.val);
tmp = tmp.next;
}
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
思路解析
将链表值存入集合。在前后指针遍历。
必会知识
- 集合比较时使用 equals()，因为装的元素的 Integer
141. 环形链表
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true。否则，返回 false。
具体题解
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode A = head;
ListNode B = head;
while (A != null && A.next != null) {
A = A.next.next;
B = B.next;
if (A == B) {
return true;
}
}
return false;
}
}
思路解析
使用快慢指针，如果有环最终一定有 A==B。如果无环，最终一定有某一方为 null。
必会知识
无
142. 环形链表 II
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
具体题解
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
} else {
fast = head;
}
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
思路解析
使用快慢指针 + 数学关系推导。当 A==B 时，退出循环，让 A 从 head 重新每次加一，最后一定会在节点处相遇。
必会知识
无
21. 合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
具体题解
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode dummy1 = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
dummy.next = list1;
dummy = dummy.next;
list1 = list1.next;
} else {
dummy.next = list2;
dummy = dummy.next;
list2 = list2.next;
}
}
if (list1 == null) {
dummy.next = list2;
} else {
dummy.next = list1;
}
return dummy1.next;
}
}
思路解析
通过 dummy 头避免边界处理麻烦，将剩余两条链挨个对比接到 dummy 头后。
必会知识
dummy 头常规写法。
ListNode dummy = new ListNode<>();
ListNode dummy1 = dummy;
2. 两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
具体题解
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ans = null;
ListNode ans1 = ans;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (ans == null) {
ans = ans1 = new ListNode(sum % 10);
} else {
ans.next = new ListNode(sum % 10);
ans = ans.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
ans.next = new ListNode(carry);
}
ans1;
}
}
思路解析
这题细节处较多。在判断还有数可加时再 new ListNode，避免出现多出的链表头。对 carry 处理要细心，退出循环后 carry 仍可能有值。
必会知识
无
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
具体题解
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; i++) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
思路解析
关键在于如何定位倒数第 k 个节点。为消除倒数第 k 个节点是头节点的影响，使用 dummy 辅助。用 first 节点先走 k 个，second 与 first 节点再一起走，走到 first=null。则 second 在倒数第 k 个的位置。
必会知识
无
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
具体题解
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode dummy1 = dummy;
while (dummy != null && dummy.next != null && dummy.next.next != null) {
ListNode node1 = dummy.next;
ListNode node2 = dummy.next.next;
dummy.next = node2;
node1.next = node2.next;
node2.next = node1;
dummy = node1;
}
return dummy1.next;
}
}
思路解析
注意力放在上一节点，当前节点，下一节点上。最开始利用 dummy 充当上一节点，重新连接这三个节点的位置，再将 dummy 赋值为下一轮次的'上一节点'。
必会知识
无
25. K 个一组翻转链表
给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
具体题解
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode cur = head;
for (int i = 0; i < k; i++) {
if (cur == null) return head;
cur = cur.next;
}
ListNode dummy = reverseKGroup(cur, k);
for (int i = 0; i < k; i++) {
ListNode tmp = head.next;
head.next = dummy;
dummy = head;
head = tmp;
}
return dummy;
}
}
思路解析
利用递归的思想，但更主要的是反转链表中的模板思路。反转链表的思路代入到这里，上一节点即为 dummy（当前 k 节点之外的节点，由递归返回），当前节点即为 head。流程是先递归，再反转。
必会知识
无
138. 随机链表的复制
给你一个长度为 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 作为传入参数。
具体题解
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Node cur = head;
Map<Node, Node> map = new HashMap<>();
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
思路解析
这里的神来之笔是，利用 hashmap 存入与待复制节点一模一样的节点，并且完成映射关系。
必会知识
无
148. 排序链表
给你链表的头结点 head，请将其按升序排列并返回排序后的链表。
具体题解
class Solution {
public ListNode sortList(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode node = head;
while (node != null) {
list.add(node.val);
node = node.next;
}
Collections.sort(list);
node = head;
int i = 0;
while (node != null) {
node.val = list.get(i);
node = node.next;
i++;
}
return head;
}
}
思路解析
将链表数值存入集合，排序后再放入链表中。
必会知识
- Collections.sort()
23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
具体题解
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null) return null;
Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode x, ListNode y) {
return x.val - y.val;
}
});
ListNode dummy = new ListNode(0);
ListNode dummy1 = dummy;
for (ListNode node : lists) {
if (node != null) {
queue.offer(node);
}
}
while (!queue.isEmpty()) {
dummy.next = queue.poll();
dummy = dummy.next;
if (dummy.next != null) {
queue.offer(dummy.next);
}
}
return dummy1.next;
}
}
思路解析
利用最小堆内部排序算法来排序链表。每次取出的链表节点都是当前最小的，将该节点接入 dummy 后，再把剩余节点加入堆中重新排序。这里注意某链表为 null 则不加入最小堆中。
必会知识
- 最小堆的自定义排序
Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode x, ListNode y) {
return x.value - y.value;
}
});
146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
具体题解
class LRUCache {
class DlinkNode {
int key;
int value;
DlinkNode next;
DlinkNode prev;
public DlinkNode() {}
public DlinkNode(int key1, int value1) {
key = key1;
value = value1;
}
}
private int size;
private int capacity;
private Map<Integer, DlinkNode> map;
private DlinkNode dummyhead = new DlinkNode();
private DlinkNode dummytail = new DlinkNode();
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
map = new HashMap<>();
dummyhead.next = dummytail;
dummytail.prev = dummyhead;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
moveToHead(map.get(key));
return map.get(key).value;
}
public {
(map.containsKey(key)) {
map.get(key).value = value;
moveToHead(map.get(key));
} {
(key, value);
addToHead(tmp);
map.put(key, tmp);
size++;
(size > capacity) {
removeTail();
size--;
}
}
}
{
node.prev.next = node.next;
node.next.prev = node.prev;
addToHead(node);
}
{
dummyhead.next;
node.prev = dummyhead;
node.next = dummyhead.next;
dummyhead.next = node;
tmp.prev = node;
}
{
dummytail.prev;
dummytail.prev = tmp.prev;
tmp.prev.next = dummytail;
map.remove(tmp.key);
}
}
思路解析
这里存储 key，value，因此主要使用 Map 数据结构存储，链表来维护 LRU 队列。链表中的 key 用来与 map 映射，方便 map.move(tmp.key)。链表中的 value 用来存储值。需要实现链表头与链表尾方便定位，实现 moveToHead，addToHead，removeTail 函数。
必会知识
- 链表的实现是一个内部类，类似 c 语言的结构体。
