这个专题算是经典中的经典了，从之前的刷题记录就可以看出，一共14题，其中5题之前都刷过。还是本着时间有限的原则，刷过的题看一下之前的记录就自己思考了，专注冲新题
首先，和二叉树一样，先构造一个链表节点的数据结构。
/*
Author Owen_Q
*/
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;
}
/**
* 构建有环链表
* @param nodes 列表元素
* @param circlePos 环位置
* @return 有环列表
*/
public static ListNode build(List<Integer> nodes, Integer circlePos) {
ListNode list = build(nodes);
int len = nodes.size();
if (circlePos != null && circlePos < len && circlePos >= 0) {
ListNode circle = list;
for (int i = 0; i < circlePos; i++) {
circle = circle.next;
}
ListNode tail = list;
while (tail.next != null) {
tail = tail.next;
}
tail.next = circle;
}
return list;
}
/**
* 构建无环链表
* @param nodes 列表元素
* @return 无环列表
*/
public static ListNode build(List<Integer> nodes) {
if (nodes == null || nodes.isEmpty()) {
return null;
}
return new ListNode(nodes.get(0), buildRecursion(nodes, 1));
}
private static ListNode buildRecursion(List<Integer> nodes, int pos) {
int len = nodes.size();
if (pos == len) {
return null;
}
return new ListNode(nodes.get(pos), buildRecursion(nodes, pos + 1));
}
public static List<Integer> toList(ListNode node) {
ListNode now = node;
ListNode circle = circleEntrance(now);
boolean hasCircle = circle != null;
List<Integer> result = new ArrayList<>();
while (now != null) {
// 若链表有环，则用null隔开链与环
if (now == circle) {
if (hasCircle) {
hasCircle = false;
} else {
break;
}
result.add(null);
}
result.add(now.val);
now = now.next;
}
return result;
}
public static ListNode circleEntrance(ListNode head) {
HashSet<ListNode> set = new HashSet<>();
ListNode now = head;
while (now != null) {
if (set.contains(now)) {
return now;
}
set.add(now);
now = now.next;
}
return null;
}
@Override
public String toString() {
return toList(this).toString();
}
}历史题
历史题刷的原则是先看之前的文章，回忆之前的心得和技巧，然后根据思路自己去写，尽可能不要画过多的时间
链表经典问题
递归法求解面试三大经典链表问题_递归遍历链表题目-CSDN博客
来个承上启下，上个专题结束前，看了之前写的一篇二叉树和链表汇总在一起的博客，上次说了二叉树篇，这次就先以剩余的两道链表题开头
206. Reverse Linked List[Easy]
思路：分递归和非递归写法，非递归就是三指针操作断链重连的过程，递归只需要将当前节点断开，然后将下一个节点指向当前节点即可，后续都可以递归完成。
不得不说五年过去了，编译器变快了，但是貌似牺牲了一点内存空间
此处，为了节约时间我们只写一下递归做法，非递归做法看之前的博客即可
/*
Author Owen_Q
*/
class ListReversor {
public static ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode reversedNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return reversedNode;
}
}21. Merge Two Sorted Lists[Easy]
思路：也分为递归和非递归。非递归用一个单独的指针去比较两个链表进行拼接，而递归就更简单了，直接复用小的链表头进行操作，将其连到递归下一项上
同样这里只做递归写法，非递归还是看原博客
/*
Author Owen_Q
*/
class ListMerger {
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}链表交点问题
142. Linked List Cycle II[Medium]
思路：最简单的方法当然是哈希法，直接用哈希表存储已经遍历过的节点，若重复读取则可以直接找到入环口，该方法直接被写在了链表数据结构的 方法中
此外双指针法思路很巧妙，先快慢指针判环，再用双指针找入口，具体思路还是看之前的原文
/*
Author Owen_Q
*/
public class CircleList2 {
public static ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}160. Intersection of Two Linked Lists[Easy]
思路：直接将链表分别正反首位相连形成两个新链表，并同时遍历两个链表，相交处即为来拿表交点。
当然，为了方便起见，这里我们也直接用哈希法来实现，链表合并法还是看之前的原文这里不再实现
/*
Author Owen_Q
*/
public class IntersectionNode {
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
Set<ListNode> set = new java.util.HashSet<>();
ListNode now = headA;
while (now != null) {
set.add(now);
now = now.next;
}
now = headB;
while (now != null) {
if (set.contains(now)) {
return now;
}
now = now.next;
}
return null;
}
}哈希法实现按键值访问链表
LeetCodeGOGOGO刷题记01——链表优化（哈希法实现按键值访问链表）_链表 优化-CSDN博客
146. LRU Cache[Medium]
思路：这题的核心就是需要同时支持按位置取值和按键值取值，普通数组可以实现按位置取值，而哈希表则可以实现按键值取值，于是可以将两种数据结构结合一下。先用一个数组存储元素的位置，再用一个哈希表将键值映射到当前值在数组中的位置。每次读取的时候，将读出来的元素重新塞到数组尾并更新哈希表。插入的时候，判断数组元素是否满，若满了，则取出数组中最靠前的元素将其在哈希表中删除即可。为了方便数组的删除，用两个变量来存储数组的有效边界即可。
这么一想，其实用数组模拟了链表，完全不需要用真正的列表数据结构即可完成操作
回看一下当年的解题思路，不免发现这么多年的工作经验还是明显有进步有效果的，特别是针对这种非算法思维而是工程实现类题目，明显能力强了很多
/*
Author Owen_Q
*/
class LRUCache {
private int capacity;
private int currentEnd;
private int currentStart;
private int currentCapacity;
private List<Pair<Integer, Integer>> cacheValue;
private Map<Integer, Integer> cachePos;
public LRUCache(int capacity) {
this.capacity = capacity;
currentStart = 0;
currentEnd = 0;
currentCapacity = 0;
cacheValue = new ArrayList<>();
cachePos = new HashMap<>();
}
public int get(int key) {
if (cachePos.containsKey(key)) {
int value = cacheValue.get(cachePos.get(key)).getValue();
cacheValue.set(cachePos.get(key), null);
cacheValue.add(new Pair<>(key, value));
cachePos.put(key, currentEnd++);
return value;
}
return -1;
}
public void put(int key, int value) {
if (get(key) == -1) {
if (currentCapacity == capacity) {
while (cacheValue.get(currentStart) == null) {
currentStart++;
}
int expiredCacheKey = cacheValue.get(currentStart).getKey();
cacheValue.set(currentStart, null);
cachePos.remove(expiredCacheKey);
} else {
currentCapacity++;
}
} else {
cacheValue.set(cachePos.get(key), null);
}
cacheValue.add(new Pair<>(key, value));
cachePos.put(key, currentEnd++);
}
}
/**
* 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);
*/新题
141. Linked List Cycle[Easy]
思路：这一题就是上面编号142题链表判环的简化版本，直接用上述代码即可
/*
Author Owen_Q
*/
public class CircleList {
public static boolean hasCycle(ListNode head) {
return CircleList2.detectCycle(head) != null;
}
}234. Palindrome Linked List[Easy]
思路：判断链表是否回文，方法有很多，主要有数组法，回溯法和链表翻转法
数组法
数组法就是将链表转化为数组，然后双指针进行判断回文
/*
Author Owen_Q
*/
public class PalindromeList()
public static boolean isPalindromeByArray(ListNode head) {
List<Integer> nodes = ListNode.toList(head);
int start = 0;
int end = nodes.size() - 1;
while (start < end) {
if (!nodes.get(start).equals(nodes.get(end))) {
return false;
}
start++;
end--;
}
return true;
}
}回溯法
回溯法就是利用递归回溯从后向前的特性，再手动记录一个从前向后的链表，即可实现收尾进行判断
/*
Author Owen_Q
*/
public class PalindromeList{
public static boolean isPalindromeRecursion(ListNode head) {
frontNode = head;
return checkPalindromeByRecursion(head);
}
private static ListNode frontNode;
private static boolean checkPalindromeByRecursion(ListNode head) {
if (head == null || frontNode == null) {
return true;
}
if (!checkPalindromeByRecursion(head.next)) {
return false;
}
if (head.val != frontNode.val) {
return false;
}
frontNode = frontNode.next;
return true;
}
}链表翻转法
思路： 首先用快慢指针找到链表中点位置，然后将后半个链表翻转，再利用双指针分别遍历链表的前后两个部分即可进行判断，最后记得将链表翻转回来即可，翻转链表可以用上面编号206题翻转链表的代码
/*
Author Owen_Q
*/
public class PalindromeList{
public static boolean isPalindromeByReverseList(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode reverseList = ListReversor.reverseList(slow);
ListNode back = reverseList;
ListNode front = head;
while (back != null) {
if (back.val != front.val) {
ListReversor.reverseList(reverseList);
return false;
}
back = back.next;
front = front.next;
}
ListReversor.reverseList(reverseList);
return true;
}
}148. Sort List[Medium]
思路：说到排序，首先先复习一下排序基础
那么链表的排序，其实最方便的还是归并排序了，接下来就用递归和非递归两种方式来实现一下
自上而下递归法
递归法相比较于非递归法，一般思路都十分清晰。首先快慢指针找到链表中点，这个时候需要预备一个pre指针用于记录中点前的节点，用于将前后链表断链。断链后将前后链表分别递归排序，最后可以用上面编号21题合并链表的代码，将前后链表合并即可
/*
Author Owen_Q
*/
class SortList {
public static ListNode sortListFromTop(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head, fast = head, pre = null;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
ListNode left = sortListFromTop(head);
ListNode right = sortListFromTop(slow);
return ListMerger.mergeTwoLists(left, right);
}
}自下而上非递归法
非递归写法就会复杂一些了，核心思路就是从小到大排序链表，先将链表分割为长度为1的子链表，然后两两合并，再将合并后的链表两两合并，依次类推最终完成排序。当然，为了避免链表先后信息丢失，每次断链的操作会在合并链表前，合并链表完成后需要立刻将链表拼接。这就需要一个pre指针来记录上一个被合并的链表，并将当前被合并的链表与之前的链表拼接。分隔链表的同时，记录分割后的位置有利于循环的向后遍历，最后在开始的时候记录一下链表长度，作为循环结束的标志即可。
/*
Author Owen_Q
*/
class SortList {
public static ListNode sortListFromBottom(ListNode head) {
int length = 0;
ListNode cur = head;
while (cur != null) {
length++;
cur = cur.next;
}
for (int i = 1; i < length; i <<= 1) {
ListNode pre = null;
cur = head;
while (cur != null) {
ListNode left = cur;
ListNode right = split(cur, i);
cur = split(right, i);
ListNode merge = ListMerger.mergeTwoLists(left, right);
if (pre == null) {
head = merge;
pre = head;
} else {
pre.next = merge;
}
while (pre.next != null) {
pre = pre.next;
}
}
}
return head;
}
private static ListNode split(ListNode head, int length) {
ListNode cur = head;
while (length > 1 && cur != null) {
cur = cur.next;
length--;
}
if (cur == null) {
return null;
}
ListNode next = cur.next;
cur.next = null;
return next;
}
}138. Copy List with Random Pointer[Medium]
思路：随机链表，在普通链表基础上，包含一个新的指针指向链表中随机的元素，现在要求将这个链表复制一份。
首先先和普通链表一样，先构造一份随机链表
/*
Author Owen_Q
*/
private static class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
private static List<Node> nodeList = new ArrayList<>();
private static Map<Node, Integer> nodePosMap = new HashMap<>();
public static Node buildNode(List<List<Integer>> nodes) {
if (nodes == null || nodes.isEmpty()) {
return null;
}
nodeList.clear();
for (List<Integer> node : nodes) {
nodeList.add(new Node(node.get(0)));
}
int nodeSize = nodeList.size();
for (int i = 0; i < nodeSize; i++) {
Node node = nodeList.get(i);
if (i != nodeSize - 1) {
node.next = nodeList.get(i + 1);
}
if (nodes.get(i).get(1) != null) {
node.random = nodeList.get(nodes.get(i).get(1));
}
}
return nodeList.get(0);
}
private List<List<Integer>> toList() {
nodePosMap.clear();
List<List<Integer>> result = new ArrayList<>();
Node cur = this;
int pos = 0;
while (cur != null) {
List<Integer> node = new ArrayList<>();
node.add(cur.val);
nodePosMap.put(cur, pos);
result.add(node);
cur = cur.next;
pos++;
}
cur = this;
pos = 0;
while (cur != null) {
List<Integer> node = result.get(pos);
node.add(nodePosMap.get(cur.random));
cur = cur.next;
pos++;
}
return result;
}
@Override
public String toString() {
return toList().toString();
}
}这一题相比较于传统链表，最大的问题就是，链表节点中的随机指针指向的节点不知道在何时会被创建出来，于是，如果能提前把链表模型建出来，再去补随机指针就是个核心思路。
哈希法
哈希法就是通过将新旧链表节点进行映射。第一轮映射完之后，第二轮遍历即可将随机指针补全
/*
Author Owen_Q
*/
public class RandomListCopyer {
private static Map<Node, Node> copyMap = new HashMap<>();
public static Node copyRandomListWithHash(Node head) {
Node cur = head;
while (cur != null) {
copyMap.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
Node copyedNode = copyMap.get(cur);
copyedNode.next = copyMap.get(cur.next);
copyedNode.random = copyMap.get(cur.random);
cur = cur.next;
}
return copyMap.get(head);
}
}链表拼接法
思路：相比于哈希法，将复制的新表节点存储在哈希映射表中。链表拼接法则直接借用了链表自身的结构，将复制表的每个节点直接连在原表的后方，依旧是两轮遍历后将随机指针补全，最后再加一轮遍历断链即可
/*
Author Owen_Q
*/
public class RandomListCopyer {
public static Node copyRandomListAfterOld(Node head) {
Node cur = head;
while (cur != null) {
Node copyedNode = new Node(cur.val);
copyedNode.next = cur.next;
cur.next = copyedNode;
cur = copyedNode.next;
}
cur = head;
while (cur != null) {
Node copyedNode = cur.next;
if (cur.random != null) {
copyedNode.random = cur.random.next;
}
cur = copyedNode.next;
}
cur = head;
Node copyedHead = head == null ? null : head.next;
while (cur != null) {
Node copyedNode = cur.next;
cur.next = copyedNode.next;
if (copyedNode.next != null) {
copyedNode.next = cur.next.next;
}
cur = cur.next;
}
return copyedHead;
}
}24. Swap Nodes in Pairs[Medium]
思路：链表俩俩交换顺序。没什么说的，就是手撕代码，一定要细一定要细一定要细！还是分递归和非递归两种方案来写，直接上代码
递归法
/*
Author Owen_Q
*/
public class ListSwapper {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
head.next = swapPairsWithRecursion(next.next);
next.next = head;
return next;
}
非递归法
/*
Author Owen_Q
*/
public class ListSwapper {
if (head == null || head.next == null) {
return head;
}
ListNode cur = head;
ListNode result = head.next;
while (cur != null && cur.next != null) {
ListNode toSwap = cur.next;
ListNode swapNext1 = toSwap.next;
ListNode swapNext2 = swapNext1;
if (swapNext2 != null && swapNext2.next != null) {
swapNext2 = swapNext2.next;
}
cur.next = swapNext2;
toSwap.next = cur;
cur = swapNext1;
}
return result;
}
19. Remove Nth Node From End of List[Medium]
思路：删除链表倒数第N个节点，由于链表前后有序，删除倒数需要两轮遍历，第一轮求链表长度，第二轮删除节点。但如果想要一轮遍历，双指针的优势就体现出来了。快指针先跑N格，慢指针用于删除
/*
Author Owen_Q
*/
public class ListEndRemover {
public static ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
if (fast == null) {
return head.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}
2. Add Two Numbers[Medium]
思路：给定两个链表，表示数字的逆序存储，求两链表和所形成的链表
还好是逆序存储，那么从低位开始直接枚举求和然后记录一下进位就行了，否则还要判断一下链表长度进行位数配对
/*
Author Owen_Q
*/
public class ListSum {
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode a1 = l1;
ListNode a2 = l2;
int now = a1.val + a2.val;
boolean addOne = now >= 10;
if (addOne) {
now -= 10;
}
ListNode result = new ListNode(now);
ListNode cur = result;
a1 = a1.next;
a2 = a2.next;
while (a1 != null || a2 != null) {
now = addOne ? 1 : 0;
if (a1 != null) {
now += a1.val;
a1 = a1.next;
}
if (a2 != null) {
now += a2.val;
a2 = a2.next;
}
if (now >= 10) {
now -= 10;
addOne = true;
} else {
addOne = false;
}
cur.next = new ListNode(now);
cur = cur.next;
}
if (addOne) {
cur.next = new ListNode(1);
}
return result;
}
}
25. Reverse Nodes in k-Group[Hard]
思路：这就是个纯手撕链表题，确实不难看出，leetcode的代码难度确实整体偏低，像这种稍微带一点逻辑的手撕题就能轻轻松松上hard了。断链，翻转，重连三步走，翻转链表可以用上面编号206题翻转链表的代码，别的也没啥好说的，直接上代码
/*
Author Owen_Q
*/
public class ListReversorForGroups {
public static ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null || k <= 1) {
return head;
}
ListNode result = head;
ListNode cur = head;
ListNode prev = null;
while (cur != null) {
ListNode groupEnd = cur;
for (int i = 1; i < k && groupEnd != null; i++) {
groupEnd = groupEnd.next;
}
if (groupEnd == null) {
return result;
}
if (result == head) {
result = groupEnd;
}
ListNode next = groupEnd.next;
if (prev != null) {
prev.next = null;
}
if (next != null) {
groupEnd.next = null;
}
groupEnd = cur;
cur = ListReversor.reverseList(cur);
if (prev != null) {
prev.next = cur;
}
if (next != null) {
groupEnd.next = next;
}
cur = next;
prev = groupEnd;
}
return result;
}
}
23. Merge k Sorted Lists[Hard]
思路：合并多个有序链表，可以俩俩链表合并，也可以多链表同事合并
分组合并法
分组合并法就是将待合并链表俩俩分组合并，合并完后，再将合并后的链表俩俩分组合并，最终直到只剩下一个链表。合并链表的过程可以参考上面编号21题合并链表的代码
/*
Author Owen_Q
*/
public class ListMergerForMultitude {
public static ListNode mergeKListsMerge2Lists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
List<ListNode> nodeQueue = new ArrayList<>(Arrays.asList(lists));
int st = 0;
int en = lists.length - 1;
while (st <= en - 1) {
nodeQueue.add(ListMerger.mergeTwoLists(nodeQueue.get(st), nodeQueue.get(st + 1)));
en++;
st += 2;
}
return nodeQueue.get(en);
}
}
优先队列法
当然也可以用优先队列，将每个列表的头节点加入优先队列，然后每次挑选最小元素出队列，再将该元素的后续节点加入队列
/*
Author Owen_Q
*/
public class ListMergerForMultitude {
public static ListNode mergeKListsPriorityQueue(ListNode[] lists) {
if (lists == null) {
return null;
}
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparing(node -> node.val));
for (ListNode list : lists) {
if (list != null) {
queue.add(list);
}
}
if (queue.isEmpty()) {
return null;
}
ListNode minNode = queue.poll();
ListNode headNode = new ListNode(minNode.val);
if (minNode.next != null) {
queue.add(minNode.next);
}
ListNode currentNode = headNode;
while (!queue.isEmpty()) {
minNode = queue.poll();
currentNode.next = new ListNode(minNode.val);
currentNode = currentNode.next;
if (minNode.next != null) {
queue.add(minNode.next);
}
}
return headNode;
}
}
完结撒花