当前位置：首页 > backend >正文

链表算法知识汇总

backend 2025/9/2 6:09:03

1.java链表

java中的链表节点都是对象，操作由对象引用来完成，以下是java链表节点的定义：

 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; }}

这些链表节点由JVM自动管理，不需要手动释放内存。

->链表和数组的比较

从以下几个方面：插入与删除性能，查询性能，适用场景

数组在创建时长度就是固定的，如果需要扩容则需要创建新的数组；数组在内存中的分布是连续的。
链表的长度不固定，能够动态的增删节点；链表节点在内存中分布不是连续的，其分配机制取决于操作系统。

ListNode node = new ListNode();

这行代码的底层实现：

调用new时，JVM向操作系统申请一块内存；
操作系统从进程的堆空间分配一块内存，并返回内存快的地址；
JVM将返回的地址存储为对象的引用。

2.java集合之List接口｜ArrayList类｜LinkedList类

List接口：通常用ArrayList类｜LinkedList类两种实现方式

// 使用 List 接口声明，而具体实现为 ArrayList
List<String> list1 = new ArrayList<>();// 使用 List 接口声明，而具体实现为 LinkedList
List<String> list2 = new LinkedList<>();

ArrayList类：底层用动态数组实现。

LinkedList类：底层用双向链表实现。

3.【算法】移除链表元素

题目：leetcode203，移除指定值的节点

思路：为了使删除头节点的操作与删除其他节点的操作统一 => 添加虚拟头节点

代码：

public ListNode removeElements(ListNode head, int val) {// 设置一个虚拟的头结点ListNode dummy = new ListNode();dummy.next = 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;
}

注意⚠️：由于要通过下一个节点的值与val比较，cur作为前缀指针，当下一个节点的值被删除后，cur指针不需要移动，这样才能比较下个节点的值。

4.【算法】设计链表

题目：leetcode707，设计一个链表类，实现增删改查

val、next属性不属于链表类，而是新定义节点类。而虚拟头节点dummy、链表长度size才属于链表类，类的定义和初始化如下：

class MyLinkedList {class ListNode {int val;ListNode next;ListNode(int val) {this.val=val;}}//size存储链表元素的个数private int size;//注意这里记录的是虚拟头结点private ListNode head;//初始化链表public MyLinkedList() {this.size = 0;this.head = new ListNode(0);}

另外，由于这个题目是根据索引进行删除、添加等，所以直接使用索引来遍历比"指针"while遍历方便很多，不容易出错。如：

public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}//因为有虚拟头节点，所以不用对index=0的情况进行特殊处理ListNode pre = head;for (int i = 0; i < index ; i++) {pre = pre.next;}pre.next = pre.next.next;size--;}

5.【算法】相交链表

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

解题思路：

注意⚠️：该题判断相交节点是判断节点是否是同一个（也就是内存中的地址相同才算同一个节点），而不是判断节点的值！！因此如果能够找到第一个相同的节点c1，那么后面的链表（c2，c3）也都会相同。

所以，可以求出A，B链表的长度，使curA指向curB相同长度的位置，也就是把两个链表尾端对齐，从短链表开头开始找第一个相同节点，比较的方式为"curA==curＢ"。

代码如下：

public class Solution {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;}}

查看全文

http://www.xdnf.cn/news/19443.html