算法学习-2、链表学习
这两天复习了链表，写了十几道链表的算法题
1、61. 旋转链表
5、32进制的两个链表加法
7、链表升序
9、约瑟夫环
10、21. 合并两个有序链表
1、61. 旋转链表
public static ListNode shiftLinkedListRightByK(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// 计算长度并找到尾节点
int length = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
length++;
}
k = k % length;
if (k == 0) {
return head;
}
// 使用快慢指针找到新的尾节点
ListNode slow = head;
ListNode fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// 重组链表
ListNode newHead = slow.next;
slow.next = null;
tail.next = head;
return newHead;
}2、19. 删除链表的倒数第 N 个结点
public static ListNode removeNthNodeFromEnd(ListNode head, int n) {
// 链表长度为0的特殊场景
if (head == null) {
return head;
}
// 链表长度为1的特殊场景
if(head.next == null && n == 1) {
return null;
}
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// 链表长度为2的情况
if(fast == null) {
return slow.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
3、143. 重排链表
public void reorderList(ListNode head) {
ListNode m1 = middleNode(head);
ListNode head2 = reverseList(m1);
while(head2.next != null){
ListNode temp1 = head.next;
ListNode temp2 = head2.next;
head.next = head2;
head2.next = temp1;
head = temp1;
head2 = temp2;
}
}
public ListNode middleNode(ListNode head){
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode reverseList(ListNode head){
if (head == null || head.next == null) {
return head;
}
ListNode prev = null;
ListNode curr = head;
while(curr != null){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}4、142. 环形链表 II
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){ // 如果相等的话，那证明一定有环
fast = head; // 根据fast = 2slow, head到环的入口的距离 一定=相遇节点继续走到入口节点的距离
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}5、32进制的两个链表加法
给定两个 非空链表 L1和 L2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一个字符（0 - 9，a - z）。将这两数相加会返回一个新的链表。备注：a 代表 10， b 代表 11，以此类推
可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例 1：
第一个数：'1' -> 'a' -> 'z' （对应 1az）
第二个数：'2' -> 'b' -> 'y' （对应 2by）
相加得到：'3' -> 'n' -> '5' (对应 3n5)
示例 2：
第一个数：'9' -> '0' -> '1' （对应 901）
第二个数：'1' -> 'b' -> '3' -> '5' （对应 1b35）
相加得到：'1' -> 'k' -> '3' -> '6' (对应 1k36)
难点：
1、每个节点存储的都是字符类型
解决方案：可以设计两个方法，字符转成整数，整数转成字符
2、字符类型需要相加并且进位
解决方法：通过一个额外的变量保存进位import java.util.List;
public class LinkNodeAlgorithm {
/**
* 内部类
*/
private class ListNode {
private int value;
private ListNode next;
public ListNode(int value) {
this.value = value;
next = null;
}
}
/**
* 建立链表
*
* @param arr
* @return
*/
public ListNode createLinkList(int[] arr) {
ListNode head = new ListNode(0);
ListNode res = head;
for (int i = 0; i < arr.length; i++) {
ListNode listNode = new ListNode(arr[i]);
head.next = listNode;
head = head.next;
}
return res.next;
}
/**
* 打印链表
*/
public void printLinkedList(ListNode head) {
while (head != null) {
if (head.next != null) {
System.out.print(head.value + "->");
} else {
System.out.println(head.value);
}
head = head.next;
}
}
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5};
LinkNodeAlgorithm linkNodeAlgorithm = new LinkNodeAlgorithm();
ListNode linkList1 = linkNodeAlgorithm.createLinkList(arr);
linkNodeAlgorithm.printLinkedList(linkList1);
// ListNode listNode = shiftLinkedListRightByK(linkList1, 2);
// linkNodeAlgorithm.printLinkedList(listNode);
ListNode linkList2 = reorderLinkedList(linkList1);
linkNodeAlgorithm.printLinkedList(linkList2);
}
/**
* 第一题:链表的每个节点右移K个位置
* 例如：
* - 输入：1 -> 2 -> 3 -> 4 -> 5, K = 2
* - 输出：4 -> 5 -> 1 -> 2 -> 3
*/
public static ListNode shiftLinkedListRightByK(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// 计算长度并找到尾节点
int length = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
length++;
}
k = k % length;
if (k == 0) {
return head;
}
// 使用快慢指针找到新的尾节点
ListNode slow = head;
ListNode fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// 重组链表
ListNode newHead = slow.next;
slow.next = null;
tail.next = head;
return newHead;
}
/**
* 第二题:删除链表的倒数第n个节点
* 示例 1：
* 输入：head = [1,2,3,4,5], n = 2
* 输出：[1,2,3,5]
* 示例 2：
* 输入：head = [1], n = 1
* 输出：[]
* 示例 3：
* 输入：head = [1,2], n = 1
* 输出：[1]
*/
public static ListNode removeNthNodeFromEnd(ListNode head, int n) {
// 链表长度为0的特殊场景
if (head == null) {
return head;
}
// 链表长度为1的特殊场景
if(head.next == null && n == 1) {
return null;
}
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// 链表长度为2的情况
if(fast == null) {
return slow.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
/**
* 第三道:重排链表
* 示例 1：
* 输入：head = [1,2,3,4]
* 输出：[1,4,2,3]
* 示例 2：
* 输入：head = [1,2,3,4,5]
* 输出：[1,5,2,4,3]
*/
public static ListNode reorderLinkedList(ListNode head) {
ListNode mid = searchMiddleNode(head);
ListNode head2 = reverseLinkedList(mid);
ListNode res = head;
while (head2.next != null) {
ListNode nxt = head.next;
ListNode nxt2 = head2.next;
head.next = head2;
head2.next = nxt;
head = nxt;
head2 = nxt2;
}
return res;
}
/**
* 第四道:链表是否有环,链表判断是否有环，如果有环，返回环的入口
* @return
*/
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){ // 如果相等的话，那证明一定有环
fast = head; // 根据fast = 2slow, head到环的入口的距离 一定=相遇节点继续走到入口节点的距离
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
/**
* 找到中间节点
* @return
*/
public static ListNode searchMiddleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
/**
* 反转链表
* @param head
* @return
*/
public static ListNode reverseLinkedList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode tmp = curr.next;
curr.next = prev;
prev = curr;
curr = tmp;
}
return prev;
}
}
6、24. 两两交换链表中的节点
// 迭代版
public static ListNode swapPairsInLinkedList(ListNode head){
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode prev = dummyNode;
while (prev.next != null && prev.next.next != null){
ListNode first = prev.next;
ListNode second = first.next;
first.next = second.next;
second.next = first;
prev.next = second;
prev = prev.next;
}
return dummyNode.next;
}// 递归版
public static ListNode swapPairsInLinkedListByRecursion(ListNode head){
// 递归终止条件：当前节点为空或只剩一个节点
if(head != null && head.next != null){
return head;
}
// 保存下一组的头节点
ListNode nextGroupHead = head.next.next;
// 交换当前两个节点
ListNode newHead = head.next;
newHead.next = head;
// 递归处理剩余链表，并连接结果
head.next = swapPairsInLinkedListByRecursion(nextGroupHead);
return newHead;
}7、链表升序
一个链表，单索引是递增的，双索引是递减的，请对它进行升序排序，要求O(1)空间复杂度
示例 1:
public static ListNode sortWaveLinkedList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 分割奇偶链表
ListNode oddDummy = new ListNode(0);
ListNode evenDummy = new ListNode(0);
ListNode oddTail = oddDummy;
ListNode evenTail = evenDummy;
ListNode current = head;
boolean isOdd = true;
while (current != null) {
if (isOdd) {
oddTail.next = current;
oddTail = oddTail.next;
} else {
evenTail.next = current;
evenTail = evenTail.next;
}
current = current.next;
isOdd = !isOdd;
}
oddTail.next = null;
evenTail.next = null;
ListNode oddHead = oddDummy.next;
ListNode evenHead = evenDummy.next;
// 反转偶数链表
evenHead = reverseLinkedList(evenHead);
// 合并两个有序链表
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (oddHead != null && evenHead != null) {
if (oddHead.value <= evenHead.value) {
tail.next = oddHead;
oddHead = oddHead.next;
} else {
tail.next = evenHead;
evenHead = evenHead.next;
}
tail = tail.next;
}
// 连接剩余节点
tail.next = (oddHead != null) ? oddHead : evenHead;
return dummy.next;
}8、146. LRU 缓存
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private int capacity;
private Map<Integer, ListNode> map;
private ListNode dummyHead;
private ListNode dummyTail;
private class ListNode {
int key;
int value;
ListNode next;
ListNode prev;
public ListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.dummyHead = new ListNode(-1, -1);
this.dummyTail = new ListNode(-1, -1);
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
ListNode node = map.get(key);
remove(node);
update(node);
return node.value;
}
private void update(ListNode node) {
node.next = dummyHead.next;
node.next.prev = node;
node.prev = dummyHead;
dummyHead.next = node;
}
private void remove(ListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
ListNode listNode = map.get(key);
listNode.value = value;
remove(listNode);
update(listNode);
} else {
ListNode listNode = new ListNode(key, value);
map.put(key, listNode);
update(listNode);
if (map.size() > capacity) {
map.remove(dummyTail.prev.key);
remove(dummyTail.prev);
}
}
}
}
9、约瑟夫环问题
约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。
首先A开始报数，他报1。侥幸逃过一劫。
然后轮到B报数，他报2。非常惨，他被杀了
C接着从1开始报数
接着轮到A报数，他报2。也被杀死了。
最终胜利者是C
/**
* 解决约瑟夫环问题， 因为是学习链表，故本题采用链表，模拟流程来解决本问题。
*/
public class SolveJosephusProblem {
/**
* 内部类
*/
private static class ListNode {
private int value;
private ListNode prev;
private ListNode next;
public ListNode(int value) {
this.value = value;
this.prev = this;
this.next = this;
}
}
/**
* 打印链表
*/
public static void printLinkedList(ListNode head) {
while (head != null) {
if (head.next != null) {
System.out.print(head.value + "->");
} else {
System.out.println(head.value);
}
head = head.next;
}
}
/**
* 解决约瑟夫环问题
*/
public static ListNode solveJosephusProblem(int num, int removeKey){
// 模拟过程
ListNode head = new ListNode(1);
ListNode curr = head;
for (int i = 2; i <= num; i++) {
ListNode newNode = new ListNode(i);
newNode.prev = curr;
newNode.next = head;
curr.next = newNode;
head.prev = newNode;
curr = newNode;
}
// 找到指定位置,并移除它
curr = head;
while (curr.next != curr){
for (int i = 1; i < removeKey; i++) {
curr = curr.next;
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
curr = curr.next;
}
return curr;
}
public static void main(String[] args) {
ListNode listNode = solveJosephusProblem(1, 1);
System.out.println(listNode.value);
}
}10、21. 合并两个有序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode res = dummy;
while(list1 != null && list2 != null){
if(list1.val <= list2.val) {
dummy.next = list1;
list1 = list1.next;
}else {
dummy.next = list2;
list2 = list2.next;
}
dummy = dummy.next;
}
dummy.next = (list1 != null) ? list1 : list2;
return res.next;
}11、LCR 024. 反转链表
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}12、25. K 个一组翻转链表
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 1) return head; // 特判 k=1 直接返回
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupEnd = dummy; // 前一组的尾节点
while (head != null) {
// 1. 找到当前组的起始和结束节点
ListNode groupStart = head;
ListNode groupEnd = getKthNode(groupStart, k);
if (groupEnd == null) break; // 剩余节点不足 k 个
// 2. 断开当前组与下一组的连接
ListNode nextGroupStart = groupEnd.next;
groupEnd.next = null;
// 3. 反转当前组，并连接前后组
ListNode newHead = reverse(groupStart); // 反转后新头
ListNode newTail = groupStart; // 反转后新尾（即原头）
prevGroupEnd.next = newHead; // 前组尾 -> 新头
newTail.next = nextGroupStart; // 新尾 -> 后组头
// 4. 更新指针，准备处理下一组
prevGroupEnd = newTail;
head = nextGroupStart;
}
return dummy.next;
}
// 辅助方法：找到从 start 出发的第 k 个节点（允许中途判空）
private ListNode getKthNode(ListNode start, int k) {
ListNode curr = start;
for (int i = 1; i < k && curr != null; i++) {
curr = curr.next;
}
return curr; // 可能为 null（不足 k 个）
}
// 辅助方法：迭代反转链表，返回新头节点
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev; // 新头节点
}
}13、82. 删除排序链表中的重复元素 II
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curr = dummy;
while (curr.next != null && curr.next.next != null) {
// 发现重复起点
if (curr.next.val == curr.next.next.val) {
int val = curr.next.val;
ListNode end = curr.next; // 从第一个重复节点开始找终点
// 定位到最后一个重复节点
while (end.next != null && end.next.val == val) {
end = end.next;
}
// 跳过所有重复节点（一次性删除）
curr.next = end.next;
} else {
// 无重复则正常移动
curr = curr.next;
}
}
return dummy.next;
}算法学习-2、链表学习
https://www.orioncoder.cn/archives/suan-fa-xue-xi-2-lian-biao-xue-xi