3. 链表
3.1 单向链表和双向链表
单项：有一个next，双向：last，next
3.2 删除链表的倒数第n个结点
1. 题目
https://leetcode.cn/problems/SLwz0R/
给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
输入：head = [1], n = 1
输出：[]
输入：head = [1,2], n = 1
输出：[1]
2. 思路
两个指针，第一个先走n-1步（倒数第一个走0步，倒数第二个走1步），然后同时移动，当第一个指针到头，第二个的位置就是待删除的节点。
注意：实际删除需要节点前一个位置，所以说走n步。
3. 代码
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
ListNode h1 = new ListNode();
h1.next = head;
ListNode p1 = h1,p2 = h1;
// 走n+1步的话，也就是 i <= n,下面要对应着p2 != null
for(int i = 0; i < n && p2 != null; i++){
p2 = p2.next;
}
while(p2.next != null){
p1 = p1.next;
p2 = p2.next;
}
p1.next = p1.next == null? null:p1.next.next;
return h1.next;
}
3.3 链表中环的入口节点
1. 题目
https://leetcode.cn/problems/c32eOV
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
2. 思路
哈希表存访问过的节点，第一个访问重复的就是入口。时间O(n)，空间O(n);
快慢指针：快指针走两步，慢指针走一步，相交的时候，从head有一个节点出发，一次一步，和慢指针相遇的时候就是入口。
假设head距离入口的长度为a，相遇点是距离入口有b个单位，再走c个单位可以回到入口处。
1. 因为fast比slow快1，所以说，每次相对于慢指针多移动一个单位，这样就说明一旦有环一定会相交。
2. slow移动的距离：a+b(因为快指针每次比慢指针多移动一个，所以在慢指针走完一圈之前，一定会相遇)。
3. fast移动的距离：a+b+n(b+c)
4. 另有 2slow的距离 = fast
5. 根据2，3，4 => 2(a+b) = a+b+n(b+c) => a = n(b+c)-b;
6. 由于我们想要a和一个正数的关系，所以 a = (n-1)(b+c) +c;
7. 由于是环，所以(n-1)(b+c)可以无视，即 a = c;
8. 所以可以让一个指针从head开始走，距离入口距离a；此时slow在交点，距离入口距离c，因为a=c，所以二者一定在入口相遇。
3. 代码
哈希表：
public ListNode detectCycle(ListNode head) {
ListNode p = head;
HashSet<ListNode> hm = new HashSet<>();
while(p != null && !hm.contains(p)){
hm.add(p);
p = p.next;
}
return p;
}
快慢指针：
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
fast = fast.next == null? null:fast.next.next;
slow = slow.next;
while(fast != null && fast != slow){
fast = fast.next == null? null:fast.next.next;
slow = slow.next;
}
if(fast == null){
return null;
}
ListNode p = head;
while(p != slow){
p = p.next;
slow = slow.next;
}
return p;
}
3.5 最近最少使用缓存(LRU)
1. 题目
https://leetcode.cn/problems/OrIXps/
运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。
实现 LRUCache 类：
-
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
-
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
-
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
2. 思路
需要思考,如何O(1)完成增删改查.
为了查找O(1)必须使用Hash; 而为了O(1)把数据放到最前,并且后面前移,必须要链表完成.
链表如何O(1)找到值呢? Hash中存节点, 这个节点就是链表那个位置的值.
由于需要根据val找到key进而删除掉map里的内容，所以需要node中有key和val
3. 代码
class Node{
int val;
int key;
Node prev;
Node next;
public Node(){}
public Node(int _key,int _val){
val = _val;
key = _key;
}
}
class LRUCache {
Node head;
Node tail;
HashMap<Integer,Node> hm;
int capacity;
public LRUCache(int capacity) {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
hm = new HashMap<>();
this.capacity = capacity;
}
public int get(int key) {
// 通过HashMap得到，并且放在队列的最前面
if(!hm.containsKey(key)){
return -1;
}
Node cur = hm.get(key);
// 断开连接
remove(cur);
// 插入头
moveToHead(cur);
return cur.val;
}
public void put(int key, int value) {
// 是否已经存在
if(hm.containsKey(key)){
Node cur = hm.get(key);
cur.val = value;
remove(cur);
moveToHead(cur);
// hm.put(key,cur);
}else{
// 不存在就需要加入新的
Node cur = new Node(key,value);
// 删除尾部
if(hm.size() >= capacity){
// 这里想删除hashmap里的值的时候发现，找不到key
// 所以在node中把key也带上吧
// System.out.print(tail.prev.val+" "+tail.prev.key+" ");
hm.remove(tail.prev.key);
// System.out.println(hm.containsKey(tail.prev.key));
remove(tail.prev);
}
// 添加新的
hm.put(key,cur);
moveToHead(cur);
}
}
public void remove(Node cur){
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
public void moveToHead(Node cur){
cur.next = head.next;
cur.prev = head;
head.next.prev = cur;
head.next = cur;
}
}
3.6 链表回文
1. 题目
https://leetcode.cn/problems/aMhZSa/
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
2. 思路
思路1 ： 用栈，正序和倒序是否一样
第一遍所有值压栈，第二遍栈和链表同时比较，栈弹出，链表next，看是不是一样
思路2： 不用栈，
- 找中点（或者上中点（偶数情况）），
- 右侧链表反转，L-> -> | <- <-R这样的结构
- LR同时向中间遍历，直到为空或者不一样。
- 空为回文，不一样不是回文
3. 代码
不用栈：
/**
* 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 void print(String s){
System.out.println(s);
}
public boolean isPalindrome(ListNode head) {
ListNode p = head;
// 获取长度
int len = 0;
while(p != null){
len++;
p = p.next;
}
// print(len+"");
// 找到中间节点
int half = len%2 == 0?len/2-1:len/2;
p = head;
while(half > 0 && p != null){
p = p.next;
half--;
}
// print(p.val+"");
// 保存下半部分，并且断开链表
ListNode r = p== null?null:p.next;
if(p != null) p.next = null;
// 翻转中间节点到tail
ListNode pre = null;
ListNode cur = r;
ListNode next = r == null?null:r.next;
while(cur != null){
cur.next = pre;
pre = cur;
cur = next;
next = next == null?null:next.next;
}
// 查看mid-tail反转后的样子
// while(pre != null){
// print(pre.val+"");
// pre = pre.next;
// }
//逐个比对看是否一致（内容，长度）
r = pre;
ListNode l = head;
// 比较内容
while(l != null && r != null){
if(l.val != r.val) return false;
ListNode lNext = l.next==null?null:l.next;
ListNode rNext = r.next==null?null:r.next;
l = lNext;
r = rNext;
}
// 偶数情况：长度必须一样
if(len%2 == 0){
if(l == null && r == null) return true;
}else{
// 奇数情况：left可以多一个
if(l != null && l.next == null) return true;
}
return false;
}
}
3.7 重排链表
1. 题目
https://leetcode.cn/problems/LGjMqU/
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例1：
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例2：
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
2. 思路
先找合并后的最后节点，
对于奇数，快慢指针可以找到中点
对于偶数，快慢指针可以找到中后的一个节点
不管奇数还是偶数，快慢指针都能直接找到最后一个节点。
最后的那个节点next置为空。从这个点开始分为两个链表。命名为表1和表2。
因为是逆序，所以先给表2翻转一下。
之后表1和表2向表1合并（因为最后一个节点一定在表1）。
3. 代码
public void reorderList(ListNode head) {
// 1. 找交换后最后一个位置的节点---> 这个位置的节点需要next = null
// 1.1 快慢指针
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
// 1.2 保留第二个节点的头
ListNode head2 = slow.next;
slow.next = null;
// 2. 翻转这个位置的下一个开始到末尾的节点，保存头
ListNode prev = null;
ListNode curr = head2;
ListNode next = head2 == null? null : head2.next;
while(curr != null){
curr.next = prev;
prev = curr;
curr = next;
next = next == null? null : next.next;
}
head2 = prev;
// while(head2 != null){
// System.out.println(head2.val);
// head2 = head2.next;
// }
// 3. 合并分开后的两个数组
ListNode index1 = head;
ListNode index2 = head2;
while(index1 != null && index2 != null){
ListNode next1 = index1.next;
ListNode next2 = index2.next;
// 添加
index1.next = index2;
index2.next = next1;
// 前进
index1 = next1;
index2 = next2;
next1 = next1 == null ? null : next1.next;
next2 = next2 == null ? null : next2.next;
}
}
3.8 链表Partition
1. 题目
给定一个链表，和一个值v，要求所有比v大的放右面，比v小的放左面，等于v的放中间。
2. 思路
六个变量分别保存，三段（小中大）的头尾，把原本链表里的节点，分别加入到头尾中。
合并需要注意，三段是否为空。
3. 代码
public static Node listPartition(Node head, int pivot) {
Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node mH = null; // big head
Node mT = null; // big tail
Node next = null; // save next node
// every node distributed to three lists
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
} else if (head.value == pivot) {
if (eH == null) {
eH = head;
eT = head;
} else {
eT.next = head;
eT = head;
}
} else {
if (mH == null) {
mH = head;
mT = head;
} else {
mT.next = head;
mT = head;
}
}
head = next;
}
// 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
if (sT != null) { // 如果有小于区域
sT.next = eH;
eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
}
// 下一步，一定是需要用eT 去接 大于区域的头
// 有等于区域，eT -> 等于区域的尾结点
// 无等于区域，eT -> 小于区域的尾结点
// eT 尽量不为空的尾巴节点
if (eT != null) { // 如果小于区域和等于区域，不是都没有
eT.next = mH;
}
return sH != null ? sH : (eH != null ? eH : mH);
}
3.9 链表相交 -- 缺代码
1. 题目
给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null 。
如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
2. 思路
首先判断有没有环：Set或者快慢指针可以搞定。
之后分情况讨论：
- A有环，B无环，没有相交。
- A，B无环，如果A，B末尾相等代表有重复。
求出到AB长度，比如A为100，B为80，让A先走20，他俩相等的地方就是第一个节点。
或者i1遍历A，i2遍历B，到头之后换一遍，i1遍历B，i2遍历A，二者第一次相等的地方就是交点。
- A,B有环
有环不相交：A遍历入环点，看能否找到B的入环点，如果找不到，就是有环不想交。
在环内相交： A遍历入环点，看能否找到B的入环点，如果找得到，就是有环相交，交点为B或者A的入环点，两个都可以。
标签：03,head,ListNode,next,链表,null,节点 From： https://www.cnblogs.com/ylw-blogs/p/17818900.html在环入口之前相交：入环点一致，入环点作为终止条件，之后按照无环判断相交。