算法笔记(链表)

news/2024/12/23 5:50:41/

leetcode24 两两交换链表

public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode();ListNode cur = dummy;cur.next = head;/*dummy -> 1 -> 2 -> 3 -> 4|      |          |cur     temp      temp1要操作的数是cur之后的两个数，如果next为空则是偶数个，next的next为空是奇数个*/while (cur.next != null || cur.next.next != null) {ListNode temp = cur.next;ListNode temp1 = cur.next.next.next;cur.next = cur.next.next;cur.next.next = temp;temp.next = temp1;cur = cur.next.next;}return dummy.next;
}

leetcode206 翻转链表

递归解法

public ListNode reverseList(ListNode head) {//递归解法ListNode pre = null;ListNode cur = head;return reverse(pre, cur);
}private ListNode reverse(ListNode pre, ListNode cur) {if (cur == null) {return pre;}ListNode temp = cur.next;cur.next = pre;return reverse(cur, temp);
}

非递归解法

public ListNode ReverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;
}

leetcode92 翻转链表二

public ListNode reverseBetween(ListNode head, int left, int right) {if (head == null || left >= right) {return head;}ListNode dummy = new ListNode();dummy.next = head;ListNode p0 = dummy;//寻找规定的首结点for (int i = 0; i < left - 1; i++) {p0 = p0.next;}ListNode cur = p0.next;ListNode pre = null;for (int i = 0; i < right - left + 1; i++) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}p0.next.next = cur;p0.next = pre;return dummy.next;
}

leetcode83 删除排序链表中的重复元素

public ListNode deleteDuplicates(ListNode head) {if (head == null) {return head;}ListNode cur = head;while (cur.next != null) {if (cur.val == cur.next.val) {//删除下一个结点cur.next = cur.next.next;} else {//否则cur向后移动cur = cur.next;}}return head;
}

leetcode203 移除链表元素

删除元素要从他的前一个元素操作

public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}ListNode dummy = new ListNode(0, head);ListNode cur = dummy;while (cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next;} else {cur = cur.next;}}return dummy.next;
}

leetcode82 删除排序中的重复元素二

 public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(0, head);ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {int val = cur.next.val;if (cur.next.next.val == val) {while (cur.next != null && cur.next.val == val) {cur.next = cur.next.next;}} else {cur = cur.next;}}return dummy.next;
}

leetcode19 删除倒数第n个结点

//方法一：双指针
public ListNode removeNthFromEnd(ListNode head, int n) {//双指针，先初始化ListNode dummy = new ListNode(0, head);ListNode right = dummy;while (n-- > 0) {right = right.next;}ListNode left = dummy;while (right.next != null) {left = left.next;right = right.next;}left.next = left.next.next;return dummy.next;
}

//方法二：倒序遍历，正序删除
public ListNode removeNthFromEnd(ListNode head, int n) {int len = 0;ListNode dummy = new ListNode(0, head);ListNode index = dummy;while (index.next != null) {len++;index = index.next;}ListNode cur = dummy;int t = len - n;while (t-- > 0) {cur = cur.next;}cur.next = cur.next.next;return dummy.next;
}

leetcode160链表相交

给你两个单链表的头节点 headA 和 headB ，
请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0, lenB = 0;while (curA != null) { // 求链表A的长度lenA++;curA = curA.next;}while (curB != null) { // 求链表B的长度lenB++;curB = curB.next;}curA = headA;curB = headB;// 让curA为最长链表的头，lenA为其长度if (lenB > lenA) {//1. swap (lenA, lenB);int tmpLen = lenA;lenA = lenB;lenB = tmpLen;//2. swap (curA, curB);ListNode tmpNode = curA;curA = curB;curB = tmpNode;}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上（末尾位置对齐）while (gap-- > 0) {curA = curA.next;}// 遍历curA 和 curB，遇到相同则直接返回while (curA != null) {if (curA == curB) {return curA;}curA = curA.next;curB = curB.next;}return null;
}

leetcode141 环形链表

public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode index1 = head;ListNode index2 = head;while (index2 != null && index2.next != null) {index1 = index1.next;index2 = index2.next.next;if (index1 == index2) {return true;}}return false;
}

leetcode142 环形链表二

思路分析：
x = 起点到入口
y = 入口到相遇点
z = 圈内剩余距离

slow = x+y
fast = x+y+n(y+z)

2(x+y) = x+y+n(y+z)

x = n(y+z)-y

x = (n-1)(y+z)+z

如果n=1则x=z

public class Solution {public ListNode detectCycle(ListNode head) {ListNode index1 = head, index2 = head;while (index2 != null && index2.next != null) {index1 = index1.next;index2 = index2.next.next;if (index2 == index1) {//判断入口ListNode slow = head;ListNode fast = index1;while (slow != fast) {slow = slow.next;fast = fast.next;}return fast;}}return null;}
}

leetcode234 回文链表

public boolean isPalindrome(ListNode head) {//用栈来模拟翻转链表Stack<Integer> stack = new Stack();//记录长度int len = 0;ListNode cur = head;while (cur != null) {stack.push(cur.val);cur = cur.next;len++;}//进行出栈操作len = len / 2;while (len-- > 0) {if (head.val != stack.pop()) {return false;}head = head.next;}return true;
}

也可以通过双指针进行判断

通过快慢指针找到中间节点，翻转后半部分链表，再依次进行比较

leetcode328 奇偶链表

public ListNode oddEvenList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode odd = head;ListNode even = head.next;//这个结点的作用是为了最后将偶数结点挂接到奇数结点之后ListNode evenHead = even;while (odd.next != null && even.next != null) {//维护奇数结点串联odd.next = even.next;odd = odd.next;//维护偶数结点串联even.next = odd.next;even = even.next;}odd.next = evenHead;return head;
}

leetcode86 分隔链表

思路：重新定义两个链表进行拼接

public ListNode partition(ListNode head, int x) {if (head == null || head.next == null) {return head;}ListNode smallHead = new ListNode(0);ListNode bigHead = new ListNode(0);ListNode small = smallHead;ListNode big = bigHead;ListNode cur = head;while (cur != null) {if (cur.val < x) {smallHead.next = cur;smallHead = smallHead.next;} else {bigHead.next = cur;bigHead = bigHead.next;}cur = cur.next;}bigHead.next = null;smallHead.next = big.next;return small.next;
}

leetcode148 排序链表

public ListNode sortList(ListNode head) {if (head == null) {return null;}ListNode res = head;ArrayList<Integer> list = new ArrayList<>();while (res != null) {list.add(res.val);res = res.next;}ListNode dummy = new ListNode(0, head);Collections.sort(list);for (int i = 0; i < list.size(); i++) {head.val = list.get(i);head = head.next;}return dummy.next;
}

leetcode146 LRU缓存

package com.sfy.LinkedListPractice;import java.util.HashMap;
import java.util.Map;public class LRUCache {//函数 get 和 put 必须以 O(1) 的平均时间复杂度运行所以必须用双向链表private class Node {int key, val;Node pre, next;Node(int key, int val) {this.key = key;this.val = val;}}//初始化容量private final int capacity;Node dummy = new Node(0, 0);Map<Integer, Node> keyNode = new HashMap<>();public LRUCache(int capacity) {this.capacity = capacity;dummy.pre = dummy;dummy.next = dummy;}public int get(int key) {Node node = getNode(key);return node == null ? -1 : node.val;}public void put(int key, int value) {//有就更新，没有就插入Node node = getNode(key);if (node != null) {node.val = value;return;}node = new Node(key, value);//新增keyNode.put(key, node);pushFront(node);//放在最前面if (keyNode.size() > capacity) {//容量过大就删除Node pre = dummy.pre;keyNode.remove(pre.key);remove(pre);}}private Node getNode(int key) {if (!keyNode.containsKey(key)) {return null;}Node node = keyNode.get(key);remove(node);//先删除pushFront(node);//再更新return node;}private void pushFront(Node node) {node.pre = dummy;node.next = dummy.next;node.pre.next = node;node.next.pre = node;}private void remove(Node node) {node.pre.next = node.next;node.next.pre = node.pre;}
}

leetcode61 旋转链表

思路一：先变成环再找新的头结点

思路二：1.全翻转 2.翻转前len-k 3.翻转后k个

public ListNode rotateRight(ListNode head, int k) {if (head == null || k == 0) {return head;}int len = 1;ListNode cur = head;while (cur.next != null) {len++;cur = cur.next;}// k = 5 - 2 - 1 = 2k = len - (k % len) - 1;cur.next = head;//变成环形链表for (int i = 0; i < k; i++) {head = head.next;}//他的下一个位置就是新的头结点ListNode newHead = head.next;//将尾节点置空head.next = null;return newHead;
}

leetcode21 合并两个有序链表

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}ListNode newHead = new ListNode();ListNode cur = newHead;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}cur = cur.next;}if (list1 != null) {cur.next = list1;}if (list2 != null) {cur.next = list2;}return newHead.next;}

http://www.ppmy.cn/news/1469797.html

相关文章

微信小程序的常用api

微信小程序的常用api

微信小程序 API 简介 微信小程序是一种不需要下载安装即可使用的应用&#xff0c;它通过微信内置的浏览器直接播放&#xff0c;提供了优秀的用户体验。小程序的核心是一套开放能力&#xff0c;其中 API 是小程序开发者最需要掌握的知识点之一。 小程序提供了丰富的 API&#…
阅读更多...
【CS.AI】AI引领编程新时代：深度探索GitHub Copilot

【CS.AI】AI引领编程新时代：深度探索GitHub Copilot

文章目录 引言0. TOP TAKEAWAYS 重要要点1. Copilot的基本功能2. 技术原理3. 优势与局限优势局限 4. 使用体验4.1 初次使用4.2 在 JetBrains 全家桶中使用 GitHub Copilot1. 安装插件2. 配置插件3. 使用 GitHub Copilot 4.3 日常开发4.4 体验与反馈 5. 对开发者生态系统的影响5…
阅读更多...
一文入门gcc

一文入门gcc

今天我们来玩玩gcc。 是因为突然发现ESP-IDF用的是CMake&#xff0c;要了解CMake最好就要先学习Makefile有个基础&#xff0c;学习Makefile最好就要先熟悉gcc&#xff0c;所以就有了今天这篇文章。 首先我们要明确一个问题&#xff0c;那就是gcc/g是什么&#xff0c;它们有什…
阅读更多...
【车载AI音视频电脑】高清车载摄像头，车载云台摄像头

【车载AI音视频电脑】高清车载摄像头，车载云台摄像头

&#xff0a; 1/3 SONY CMOS. AHD 100万&#xff0c; 200万可选 &#xff0a; 低照度&#xff0c;红外夜视功能 &#xff0a; 2.8毫米固定镜头 (2.8/3.6/4/6/8毫米镜头可选) &#xff0a; 车载专用方案 &#xff0a; 抗震&#xff0c; IP66/67防水, 防尘&#xff0c;防爆设…
阅读更多...
轨迹优化 | 图解欧氏距离场与梯度场算法(附ROS C++/Python实现)

轨迹优化 | 图解欧氏距离场与梯度场算法(附ROS C++/Python实现)

目录 0 专栏介绍1 什么是距离场&#xff1f;2 欧氏距离场计算原理3 双线性插值与欧式梯度场4 仿真实现4.1 ROS C实现4.2 Python实现 0 专栏介绍 &#x1f525;课程设计、毕业设计、创新竞赛、学术研究必备&#xff01;本专栏涉及更高阶的运动规划算法实战&#xff1a;曲线生成…
阅读更多...
鸿蒙轻内核M核源码分析系列二十 Newlib C

鸿蒙轻内核M核源码分析系列二十 Newlib C

LiteOS-M内核LibC实现有2种&#xff0c;可以根据需求进行二选一&#xff0c;分别是musl libC和newlibc。本文先学习下Newlib C的实现代码。文中所涉及的源码&#xff0c;均可以在开源站点https://gitee.com/openharmony/kernel_liteos_m 获取。 使用Musl C库的时候&#xff0c…
阅读更多...
docker和docker compose 部署

docker和docker compose 部署

一. 将微服务运行在docker上&#xff1a; 1.新建一个空文件夹docker-demo&#xff0c;在里面再新建文件夹app&#xff0c;在app目录下新建一个名为Dockerfile的文件。 2.编写Dockerfile文件 3.构建镜像 4.启动镜像 5.可以访问了。 二使用Dockerfile构建微服务镜像 1.将j…
阅读更多...
spring boot 多个项目整合，打包成可依赖的包

spring boot 多个项目整合，打包成可依赖的包

一、背景介绍 接手前人项目&#xff0c;代码都是一块一块的&#xff0c;很多个spring boot服务&#xff0c;服务器重新启动一下&#xff0c;就要同时再启动很多jar服务&#xff0c;漏一个就麻烦了&#xff08;虽然有一键启动&#xff09;。但是有很多终端黑框很是麻烦。领导要…
阅读更多...
最新文章

Copyright @ 2022~2023