算法题目总结-链表
文章目录
1.环形链表
1.答案
package com.sunxiansheng.arithmetic.day11;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 141. 环形链表
*
* @Author sun
* @Create 2025/1/16 10:36
* @Version 1.0
*/
public class t141 {
public boolean hasCycle(ListNode head) {
// 快慢指针
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// 只要相遇了，就是有环
if (slow == fast) {
return true;
}
}
return false;
}
}
2.思路
快慢指针，只要相遇，就有环
2.两数相加
1.答案
package com.sunxiansheng.arithmetic.day11;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 2. 两数相加
*
* @Author sun
* @Create 2025/1/16 10:39
* @Version 1.0
*/
public class t2 {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 结果的头节点
ListNode res = new ListNode(-1);
ListNode cur = res;
// 进位
int carry = 0;
// 遍历两个链表的指针
ListNode t1 = l1, t2 = l2;
// 只要两个链表有一个不为空就进行遍历
while (t1 != null || t2 != null) {
// 获取两个节点的值
int var1 = t1 == null ? 0 : t1.val;
int var2 = t2 == null ? 0 : t2.val;
// 求和
int sum = var1 + var2 + carry;
// 用完进位之后要恢复0
carry = 0;
// 判断是否要进位
if (sum > 9) {
carry = sum / 10;
sum = sum % 10;
}
// 给结果赋值
cur.next = new ListNode(sum);
cur = cur.next;
// 移动指针
if (t1 != null) {
t1 = t1.next;
}
if (t2 != null) {
t2 = t2.next;
}
}
// 检查是否还有没处理的进位
if (carry > 0) {
cur.next = new ListNode(carry);
}
return res.next;
}
}
2.结果
核心是有一个进位的字段，多注意即可
3.反转链表
1.答案
package com.sunxiansheng.arithmetic.day12;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 206. 反转链表
*
* @Author sun
* @Create 2025/1/17 09:56
* @Version 1.0
*/
public class t206 {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
// 哨兵节点
ListNode dummy = new ListNode(0);
dummy.next = head;
// prev
ListNode prev = dummy;
// start
ListNode start = head;
// then
ListNode then = start.next;
while (start.next != null) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
return dummy.next;
}
}
2.思路
首先需要有prev、start、then，然后只要start.next不为空，就进行反转
4.反转链表 II
1.答案
package com.sunxiansheng.arithmetic.day12;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 92. 反转链表 II
*
* @Author sun
* @Create 2025/1/17 09:52
* @Version 1.0
*/
public class t92 {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 找到prev、start、then
// 哨兵节点
ListNode dummy = new ListNode(0);
dummy.next = head;
// 让cur指向left的前一个节点作为prev
ListNode cur = dummy;
for (int i = 0; i < left - 1; i++) {
cur = cur.next;
}
ListNode prev = cur;
ListNode start = cur.next;
ListNode then = start.next;
// 遍历次数
int count = right - left;
for (int i = 0; i < count; i++) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
return dummy.next;
}
}
2.思路
找到prev、start、then，然后遍历次数为right - left
5.K 个一组翻转链表
1.答案
package com.sunxiansheng.arithmetic.day12;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 25. K 个一组翻转链表
*
* @Author sun
* @Create 2025/1/17 10:21
* @Version 1.0
*/
public class t25 {
public ListNode reverseKGroup(ListNode head, int k) {
// 哨兵节点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
// 提前记录prev
ListNode prev = dummy;
// 循环翻转
while (true) {
// 先判断有没有一组
for (int i = 0; i < k; i++) {
cur = cur.next;
// 只要发现没有一组了，就返回结果
if (cur == null) {
return dummy.next;
}
}
// 到这里就说明有一组，可以翻转链表
ListNode start = prev.next;
ListNode then = start.next;
reverseGroup(prev, start, then, k);
// 更新prev
prev = start;
// 更新cur
cur = prev;
}
}
/**
* 翻转一组链表
*
* @param prev
* @param start
* @param then
* @param k
*/
private void reverseGroup(ListNode prev, ListNode start, ListNode then, int k) {
// 翻转次数
int count = k - 1;
for (int i = 0; i < count; i++) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
}
}
2.思路
就是先判断剩下的元素够不够k个，如果够就进行反转，翻转之后要更新prev和cur
6.删除链表的倒数第 N 个结点
1.答案
package com.sunxiansheng.arithmetic.day12;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 19. 删除链表的倒数第 N 个结点
*
* @Author sun
* @Create 2025/1/17 10:44
* @Version 1.0
*/
public class t19 {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 哨兵节点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
// 求出一共有多少个节点
int count = 0;
while (cur.next != null) {
cur = cur.next;
count++;
}
// 倒数第n个节点的前一个节点的索引
int index = count - n;
cur = dummy;
while (index > 0) {
cur = cur.next;
index--;
}
// 目前cur指向了前一个节点，可以开始删除节点了
cur.next = cur.next.next;
return dummy.next;
}
}
2.思路
就是先找到一共有多少个节点，再找到倒数第n个节点的前一个节点然后删除
7.删除排序链表中的重复元素 II
1.答案
package com.sunxiansheng.arithmetic.day13;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 82. 删除排序链表中的重复元素 II
*
* @Author sun
* @Create 2025/1/19 09:32
* @Version 1.0
*/
public class t82 {
public static ListNode deleteDuplicates(ListNode head) {
// 哨兵节点
ListNode dummy = new ListNode(300);
dummy.next = head;
ListNode cur = dummy;
// 记录前一个位置
ListNode pre = dummy;
while (cur.next != null) {
cur = cur.next;
if (cur.next == null || cur.val != cur.next.val) {
pre = cur;
} else {
// 到这就说明pre的后两个元素相同
// 记录一下值
int val = cur.val;
while (cur.next != null && val == cur.next.val) {
cur = cur.next;
}
pre.next = cur.next;
cur = pre;
}
}
return dummy.next;
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(1);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(2);
head.next.next.next.next = new ListNode(3);
deleteDuplicates(head);
}
}
2.思路
就是有一个pre来记录前一个位置，每次循环都让cur先走一步，然后判断当前元素跟下一个元素是不是相同，如果不相同或者目前是最后一个元素，就让pre也指向cur，如果说当前元素跟下一个元素是相同的，那么就删除相同元素，最终让cur指向pre
8.旋转链表
1.答案
package com.sunxiansheng.arithmetic.day13;
import com.sunxiansheng.arithmetic.util.ListNode;
import java.util.List;
/**
* Description: 61. 旋转链表
*
* @Author sun
* @Create 2025/1/19 10:29
* @Version 1.0
*/
public class t61 {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
// 哨兵节点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
// 计算链表总长度
int length = 0;
while (cur.next != null) {
cur = cur.next;
length++;
}
// 如果余数为0，则直接返回
if (k % length == 0) {
return head;
}
// 记录链表末尾元素
ListNode end = cur;
// 移动到正数第length - k % length个位置
int index = length - k % length;
cur = dummy;
while (index > 0) {
cur = cur.next;
index--;
}
dummy.next = cur.next;
// 切断，否则会有环
cur.next = null;
end.next = head;
return dummy.next;
}
}
2.思路
首先计算链表的总长度，然后记录链表末尾元素，再通过计算，找到正数第length - k % length个位置，然后根据题意进行组装，不过要注意切断一下，否则会有环
9.LRU 缓存
1.答案
package com.sunxiansheng.arithmetic.day13;
import java.util.HashMap;
import java.util.Map;
/**
* Description: 146. LRU 缓存
*
* @Author sun
* @Create 2025/1/19 10:55
* @Version 1.0
*/
public 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;
}
}
// 双向链表的头尾指针
DLinkedNode head, tail;
// map：key是key，value是双向链表的节点
private Map<Integer, DLinkedNode> map;
// 容量
private int capacity;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
// 头结点和尾节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
// 获取元素
public int get(int key) {
// 从map中去获取key
DLinkedNode dLinkedNode = map.get(key);
if (dLinkedNode == null) {
return -1;
}
// 获取之后，将元素放到链表头部
moveToHead(dLinkedNode);
return dLinkedNode.value;
}
private void moveToHead(DLinkedNode dLinkedNode) {
// 首先需要在链表中删除这个元素
delete(dLinkedNode);
// 然后将元素插入到头部
insertToHead(dLinkedNode);
}
private void insertToHead(DLinkedNode dLinkedNode) {
dLinkedNode.next = head.next;
dLinkedNode.prev = head;
head.next.prev = dLinkedNode;
head.next = dLinkedNode;
}
private static void delete(DLinkedNode dLinkedNode) {
dLinkedNode.prev.next = dLinkedNode.next;
dLinkedNode.next.prev = dLinkedNode.prev;
}
// 插入或更新元素
public void put(int key, int value) {
// 先获取元素
DLinkedNode dLinkedNode = map.get(key);
// 如果元素有值了，就替换值，并移动到头部
if (dLinkedNode != null) {
dLinkedNode.value = value;
moveToHead(dLinkedNode);
} else {
// 没有值则需要新增元素
dLinkedNode = new DLinkedNode(key, value);
// 确保容量足够
ensureCapacity(map.size() + 1);
// 目前容量一定足够，直接插入到头部即可
map.put(key, dLinkedNode);
insertToHead(dLinkedNode);
}
}
private void ensureCapacity(int newSize) {
if (newSize <= capacity) {
return;
}
// 如果容量不够，则需要删除最后的一个元素
map.remove(tail.prev.key);
delete(tail.prev);
}
}
2.思路
使用双向链表+map来做
首先需要一个双向链表的类，key，value，next，prev即为属性
然后需要三个参数，双向链表的前后指针，map，容量
10.两两交换链表中的节点
1.答案
package com.sunxiansheng.arithmetic.day13;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 24. 两两交换链表中的节点
*
* @Author sun
* @Create 2025/1/19 12:01
* @Version 1.0
*/
public class t24 {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
// 提前记录prev
ListNode prev = dummy;
// 循环翻转
while (true) {
// 先判断是否有一组
for (int i = 0; i < 2; i++) {
if (cur.next == null) {
return dummy.next;
}
cur = cur.next;
}
// 到这里就是有一组了，开始翻转
ListNode start = prev.next;
ListNode then = start.next;
reverse(prev, start, then);
// 更新prev和cur
prev = start;
cur = prev;
}
}
// 两个一组翻转链表
private void reverse(ListNode prev, ListNode start, ListNode then) {
start.next = then.next;
then.next = prev.next;
prev.next = then;
then = start.next;
}
}
2.思路
就是两个一组翻转链表，翻转链表的次数是节点数减一，然后要提前记录prev，并且在翻转后更新prev和start
11.环形链表 II
1.答案
package com.sunxiansheng.arithmetic.day13;
import com.sunxiansheng.arithmetic.util.ListNode;
/**
* Description: 142. 环形链表 II
*
* @Author sun
* @Create 2025/1/19 12:31
* @Version 1.0
*/
public class t142 {
public ListNode detectCycle(ListNode head) {
// 快慢指针
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 这样只能代表有环，如果想要找到入环的第一个节点，就要让slow等于head，然后一起移动
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
2.思路
发现有环之后，如果想要找到入环的第一个节点，就要让slow等于head，然后一起移动，直到相遇
原文地址：https://blog.csdn.net/m0_64637029/article/details/145271313
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！