链表
24.两两交换链表中的节点
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null) {
return null;
}
ListNode p = new ListNode();
p.next = head;
// 考虑是奇数还是偶数
ListNode pre = p;
ListNode back = p;
ListNode tmp = p;
while (back != null && back.next != null && back.next.next != null) {
pre = pre.next; // 走一步
back = back.next.next; // 走两步
// 进行交换
tmp.next = back;
pre.next = back.next;
back.next = pre;
tmp = pre;
back = pre;
}
return p.next;
}
}其实就是需要两个指针，前指针每次走一步，后指针一次两步，然后进行节点交换，这里引入tmp的原因是因为如果只是交换当前遍历到的两个节点，那是不是会导致和前面的节点失联了，所以tmp就是指向当前正在进行交换的两个节点的前一个节点，然后它指向交换后的节点。
还有一个问题：为什么前指针每次走一步，后指针一次两步？
因为我们模拟一下就会知道，交换之后，pre在后，back在前，也就是就交换了位置，最后我们还做了一个 back = pre 操作，这样子两个都是指向后一个节点位置，所以对于pre就只需要走一步，但是back要走两步
203.移除链表元素
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode p = new ListNode(-1);
p.next = head;
ListNode cur = p.next;
ListNode pre = p;
// 进行遍历
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = pre.next;
}
cur = cur.next;
}
return p.next;
}
}本质上就是快慢指针
需要注意的一点就是pre 不是每一次都进行移动，而是当当前遍历到的节点不是val时，才会进行移动
707.设计链表
class MyLinkedList {
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public ListNode() {}
}
ListNode head;
int len;
public MyLinkedList() {
head = new ListNode(-1);
len = 0;
}
public int get(int index) {
// 先判断是否合理
if (index < 0 || index >= len) {
return -1;
}
// 移动指针
ListNode cur = head;
int cnt = 0;
while (cnt < index) {
cur = cur.next;
cnt++;
}
return cur.next.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(len, val);
}
public void addAtIndex(int index, int val) {
// 遍历找到这个位置
if (index > len) {
return;
}
if (index < 0) {
index = 0;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = new ListNode(val, cur.next);
len++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= len) return;
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
len--;
}
}class MyLinkedList {
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public ListNode() {}
}
ListNode head;
int len;
public MyLinkedList() {
head = new ListNode(-1);
len = 0;
}
public int get(int index) {
// 先判断是否合理
if (index < 0 || index >= len) {
return -1;
}
// 移动指针
ListNode cur = head;
int cnt = 0;
while (cnt < index) {
cur = cur.next;
cnt++;
}
return cur.next.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(len, val);
}
public void addAtIndex(int index, int val) {
// 遍历找到这个位置
if (index > len) {
return;
}
if (index < 0) {
index = 0;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = new ListNode(val, cur.next);
len++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= len) return;
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
len--;
}
}这道题就是简单的链表，没什么其他的解题思路
206.反转链表
class Solution {
public ListNode reverseList(ListNode head) {
// 直接使用双指针
ListNode cur = head;
ListNode pre = null;
// 1 -> 2 -> 3 -> 4 -> 5 -> 6
while (cur != null) {
// 暂存下一个节点
ListNode tmp = cur.next;
cur.next = pre; // 当前节点的下一个节点是前一个节点
pre = cur;
cur = tmp;
}
return pre;
}
}就是使用双指针进行遍历
cur复制遍历每一个元素，pre复制存储每一个元素的前一个元素，cur遍历到每一个元素都会先存储这个元素的下一个元素（方便cur修改指向之后还能指向原本的下一个元素），然后就将当前元素指向前一个元素，接着pre也指向当前元素，最后cur就可以指向下一个元素了
160. 相交链表
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 如果两链表是有共同节点的，那么走完A+B应该会等于B+A，
// 再进阶一下就是从第一个共同节点之后的节点都是相同的，可以省去一段共同节点的路程
// 那么可以变成定义两个指针，A指针就是先从完A再去走B，B指针反之，
// 如果最后能指向同一个节点就说明找到第一个共同节点了
ListNode A = headA;
ListNode B = headB;
while (A != B) {
A = A == null ? headB : A.next;
B = B == null ? headA : B.next;
}
return A;
}
}假如是相交的，可以将A链表的前面不相交部分看成是a，B前面不相交部分看成是b，最后那个相交的共同部分看成是x
如果两链表是有共同节点的，那么走完 a+x+b 应该会等于 b+x+a
所以可以使用两个指针进行两个不同顺序遍历
19.删除链表的倒数第N个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = new ListNode(-1, head);
// 定义两个指针
ListNode pre = p;
ListNode last = p;
// 快指针先走n+1步
for (int i = 0; i <= n; i++) {
last = last.next;
}
// 开始进行遍历，同步走到尾
while (last != null) {
last = last.next;
pre = pre.next;
}
pre.next = pre.next.next;
return p.next;
}
}解题思路：
其实就是使用两个指针，一快一慢，两个指针之间相隔n个节点，也就意味着要让快指针先走n+1步，然后才是同步走到最后
并且为了应对要删除的节点是首元节点的情况，还需要用一个p指针来指向head，也就是在前面再加上一个节点
最后就是进行遍历，只要当快指针执行到null的时候就说明慢指针已经到了要删除的节点的前一个节点的位置，直接修改指向，跳过要删除的那个节点就行了
234. 回文链表
class Solution {
public boolean isPalindrome(ListNode head) {
// 找中间节点
ListNode midNode = this.findMid(head);
// 进行反转
ListNode head2 = this.reverse(midNode);
// 进行判断
while (head != null && head2 != null) {
if (head.val != head2.val) {
return false;
}
head = head.next;
head2 = head2.next;
}
return true;
}
/**
* 对指定范围内的节点进行反转
* @param node
*/
private ListNode reverse(ListNode node) {
ListNode cur = node;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
/**
* 找到中间节点(如果是单数找中间，双数找中右)
* @param head
* @return
*/
private ListNode findMid(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}可以认为就是从中间节点开始，把右边的那部分节点都修改一下指向，这样子在进行从两边开始向中间进行遍历，如果是回文的话，肯定是每一个节点的值都是一样的，否则就直接返回false
所以这道题的思路就可以变成我先找到中间的节点，中开始对右边部分进行反转，最后进行判断
141. 环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
}这道题直接用快慢指针就行了，因为如果是有环的话，那么一块一慢的指针最后肯定会相遇，否则如果发现走完了还没有相遇的话肯定是无环的（可以自己想象一下在操场跑步，如果自己跑的慢，肯定是会被跑的快的人套圈的）
判断是否循环的条件就是fast.next != null && fast.next.next != null，因为fast是快于slow的，所以fast.next如果不是null的话，slow就一定不是null
142.环形链表II
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
// 现在找到了第一次相遇点
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}解题思路：接使用Floyd 判圈算法，具体的步骤就是先找到第一次相遇点，然后用两个指针，一次从相遇点开始，一次从起点开始，同频进行遍历，最后相遇点就是入环点
第一个问题：如何找到第一个相遇点？直接使用快慢指针，快指针走两步，慢指针走一步，最后相遇的点就是相遇点
第二个问题：为什么一个指针从相遇点开始，一个从链表的起点开始，进行相同步频的遍历，最后会相遇在入环点？
这个就要借助到数学证明了：
// 假设两个指针相遇时 slow走了b步，那么fast就走了2b步
// 再假设从起点到入环点的距离是a，环长是c
// 因为fast走到环内之后就是一直在进行绕圈运动，那么我们假设他多饶了k圈
// 可得fast比slow多走的距离是 2b-b = kc -> b = kc
// slow是在环中走b-a之后就相遇的，然后b-a=kc-a，
// 那我怎么知道我在环内再走几步就能到入环口呢？是不是就是找到c的整数倍的时候，也就是又回到起点
// 所以我再走a步 => (b-a)+a = (kc-a)+a = kc，此时就回到起点了
// 然后因为a是从链表起点到入环点的距离，那是不是可以推出当我找到第一次相遇点之后，我用两个指针
// 一次从相遇点开始，一次从链表起点开始，最后它们会在环的起点（入环点）相遇呢？很显然是的，因为距离都是a
其实这道题要是确实没什么思路，只是想要做出来你就行的话，直接用朴素算法标记也是可以的
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ArrayList<ListNode> listNodes = new ArrayList<>();
ListNode cur = head;
while (cur != null) {
if (listNodes.contains(cur)) {
return cur;
}
listNodes.add(cur);
cur = cur.next;
}
return null;
}
}21. 合并两个有序链表
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode p1 = list1, p2 = list2;
ListNode head = new ListNode(-1);
ListNode cur = head;
while (p1 != null && p2 != null) {
if (p1.val > p2.val) {
cur.next = p2;
cur = p2;
p2 = p2.next;
} else {
cur.next = p1;
cur = p1;
p1 = p1.next;
}
}
if (p1 != null) {
cur.next = p1;
}
if (p2 != null) {
cur.next = p2;
}
return head.next;
}
}解题思路：这道题是一道很简单的简单题，做法很简单，就是用两个指针分别进行遍历比较，然后小的那个节点就拿来拼接到head中，最后就是判断一下哪个链表还有剩余节点，直接拼接到最后（最后那两个if只会命中一个）
2. 两数相加
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1 = l1, p2 = l2;
ListNode head = new ListNode(-1);
ListNode cur = head;
int tmp = 0;
while (p1 != null || p2 != null) {
int x = (p1 != null) ? p1.val : 0;
int y = (p2 != null) ? p2.val : 0;
int sum = x + y + tmp;
tmp = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (p1 != null) p1 = p1.next;
if (p2 != null) p2 = p2.next;
}
// 如果还有溢出的话
if(tmp > 0) {
cur.next = new ListNode(tmp);
}
return head.next;
}
}解题思路：这道题就是模拟一下就行了，每次两数相加之和再加上上一次相加之和带过来的进位，进位每轮都会进行更新
还要注意链表的长度是不一定相同的饿，所以要在条件中考虑到这种情况
25. K 个一组翻转链表
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode cur = head;
int n = 0;
// 计算出长度
while (cur != null) {
n++;
cur = cur.next;
}
ListNode tmp = new ListNode(-1, head);
ListNode p = tmp;
ListNode pre = null;
cur = tmp.next;
while (n >= k) {
for (int i = 0; i < k; i++) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
// A B C
ListNode nxt = p.next; // 反转前的第一个节点
p.next.next = cur; // 反转后的最后一个节点(nxt) 连接下一组的头(cur)
p.next = pre; // 指向反转后的最后一个节点（因为反转这个这个节点应该被当成这一段的第一个节点）
p = nxt; // 移动到这一组反转后的最后一个节点，作为下一组的前驱节点
n -= k;
}
return tmp.next;
}
}这道题的解题思路其实就是对指定范围内的元素进行反转拼接，不过我们需要先遍历一遍才知道哪些节点需要进行反转
148. 排序链表
// 直接使用归并排序
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 先找到中间节点
ListNode slow = head;
ListNode fast = head.next; // 快指针先走一步的原因是假如只有两个节点，因为下面的while条件不符合，是不是就会造成两个指针都是始终指向同一个节点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 将链表拆成两个链表
ListNode midNode = slow.next; // 中间节点
slow.next = null;
// 开始进行归并排序
ListNode leftNode = sortList(head);
ListNode rightNode = sortList(midNode);
ListNode headNode = new ListNode(-1); // 要返回的节点的头节点
ListNode res = headNode; // 把要返回的头节点记录起来
while (leftNode != null && rightNode != null) {
if (leftNode.val < rightNode.val) {
headNode.next = leftNode;
leftNode = leftNode.next;
} else {
headNode.next = rightNode;
rightNode = rightNode.next;
}
headNode = headNode.next;
}
headNode.next = leftNode == null ? rightNode : leftNode;
return res.next;
}
}解题思路：这道题其实就是用归并排序，将链表无限的进行拆分，直到只有一个节点，然后进行比较
注意：fast要先走一步，因为假如只有两个节点，那么下面的while条件不符合，是不是就会造成两个指针都是始终指向同一个节点，所以只能先走一步才能解决这个问题
23. 合并 K 个升序链表
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
// 直接维护一个优先队列
Queue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
// 将各个链表的首节点入队
for (ListNode node : lists) {
if (node != null) {
priorityQueue.offer(node);
}
}
ListNode head = new ListNode(-1);
ListNode cur = head;
while (!priorityQueue.isEmpty()) {
// 取出元素
ListNode poll = priorityQueue.poll();
cur.next = poll;
// 还有下一个节点，直接入队
if (poll.next != null) {
priorityQueue.offer(poll.next);
}
cur = cur.next;
}
return head.next;
}
}解题思路：这道题就是直接每次都遍历每一个链表的节点，然后进行比较，取小得那个，但是如果是按照思路直接来实现的话，需要维护lists.length个指针，但是我们可以考虑到使用队列来存储，使用优先队列（自动进行排序），先将每一个链表的首节点存进去，然后每次取出一个节点之后还要判断一下这个节点是否有下一个节点，有的话也需要放到队列中进行排序。
146. LRU 缓存
class LRUCache {
class Cache {
int key;
int value;
Cache prev;
Cache next;
public Cache(int key, int value) {
this.key = key;
this.value = value;
}
}
private int capacity;
private int size;
private Map<Integer, Cache> map;
private Cache head; // 虚拟头节点
private Cache tail; // 虚拟尾节点
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
this.map = new HashMap<>();
this.head = new Cache(-1, -1);
this.tail = new Cache(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
// 开始进行移动操作
Cache cache = map.get(key);
removeNode(cache);
addToTail(cache);
return cache.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Cache cache = map.get(key);
cache.value = value;
removeNode(cache);
addToTail(cache);
} else {
Cache cache = new Cache(key, value);
addToTail(cache);
map.put(key, cache);
size++;
if (size > capacity) {
removeLastCache();
}
}
}
private void addToTail(Cache cache) {
cache.prev = tail.prev;
tail.prev.next = cache;
cache.next = tail;
tail.prev = cache;
}
private void removeNode(Cache cache) {
cache.prev.next = cache.next;
cache.next.prev = cache.prev;
}
private void removeLastCache() {
Cache cache = head.next;
removeNode(cache);
map.remove(cache.key);
size--;
}
}解题思路：其实就是使用map+双向链表来实现
双向链表主要是为了实现存储数据且通过头尾指针来标识访问的先后顺序，每次都插入到tail，如果要移除的话就是从head开始移除
map的作用是用来实现O(1)查找元素