在学习链表之前，现在解决在数据结构——数组的学习最后给出的简单的算法题：
leetcode，1. 找出可整除性得分最大的整数：
给你两个下标从 0 开始的整数数组 nums 和 divisors 。
divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。
返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。
public int maxDivScore(int[] nums, int[] divisors) {//cut 记录中间结果，用于更新最大得分//ans 最终结果，并当得分相同时，取数值小的返回int cnt = -1, ans = 0;//依次遍历divisor，计算其可整除得分for (int i = 0; i < divisors.length; i++) {int tmp = 0;for(int j = 0; j < nums.length; j++) {if (nums[j] % divisors[i] == 0) {tmp++;}}//更新最大得分和返回值if (tmp > cnt || (tmp == cnt && divisors[i] < ans)) {cnt = tmp;ans = divisors[i];}}return ans;}
链表的概念
上图显示的就是一个简单的链表。链表是由一系列节点组成的数据结构，其中每个节点都包含数据和指向下一个节点的引用。每个节点都连接着下一个节点，形成了一种线性序列。与数组不同，链表中的节点在内存中可以存储在不连续的位置，因此链表具有更灵活的内存使用方式。
从链表的概念中，我们可以发现其特点：
1. 由一系列节点组成，节点分成数据和指针两部分
2. 链表在内存中的存储不连续
3. 链表也是一种线性序列
学习链表，通常会将它与数组进行比较：
通过上面的表格，数组与链表的异同一目了然，根据不同的特点，选择不同的数据结构。
链表的实现
链表的实现通常包括两个类：节点类和链表类。节点类表示链表中的每个节点，包含一个数据字段和一个指向下一个节点的指针。链表类则负责管理节点之间的连接关系。
让我们看一下简单的链表的实现（Java代码）：
//定义链表节点的结构class ListNode {int val; // 数据ListNode next; //指针ListNode(int val) {this.val = val;}}//定义链表类public class LinkedList {private ListNode head;public LinkedList() {this.head = null;}// 插入节点到链表尾部public void insert(int val) {ListNode newNode = new ListNode(val);if (head == null) {head = newNode;} else {ListNode curr = head;while (curr.next != null) {curr = curr.next;}curr.next = newNode;}}//根据index,查询指定的节点并返回public ListNode getNodeAtIndex(ListNode head, int index) {if (head == null || index < 0){return null;}ListNode current = head;int count = 0;while (current != null) {if (count == index)return current;count++;current = current.next;}return null; // 如果链表长度小于index，返回null}// 遍历链表并打印节点值public void display() {ListNode curr = head;while (curr != null) {System.out.print(curr.val + " ");curr = curr.next;}System.out.println();}}
着重学习下链表的插入和删除操作：
要在链表中插入节点，首先需要找到要插入位置的前一个节点，然后将新节点插入到其后面。如图：
//指定位置，插入指定的节点public void insertNode(ListNode head, int position, int value) {if (head == null || position < 0)return;ListNode newNode = new ListNode(value);if (position == 0) {newNode.next = head;head = newNode;return;}ListNode prev = null;ListNode current = head;int count = 0;while (current != null && count < position) {prev = current;current = current.next;count++;}if (count == position) {prev.next = newNode;newNode.next = current;} else {System.out.println("Position out of bounds");}}
当你删除链表中的一个节点时，你需要更新前一个节点的 next 指针，使其跳过被删除的节点，指向被删除节点的下一个节点。这样就可以将被删除节点从链表中移除。如图：
//删除指定的节点public ListNode deleteNode(ListNode head, int position) {if (head == null || position < 0)return head;if (position == 0)return head.next;ListNode prev = null;ListNode current = head;int count = 0;while (current != null && count < position) {prev = current;current = current.next;count++;}if (count == position && current != null) {prev.next = current.next;}return head;}
链表的应用
链表在实际中有广泛的应用，包括但不限于以下几个领域：
- 大名鼎鼎的区块链的实现
- 数据结构：栈、队列、图等数据结构可以使用链表来实现。
- 内存管理：动态内存分配和释放时，链表可以帮助管理内存的分配情况。
- 文件操作：链表可以用于处理大型文件的读取和写入操作，以及记录文件系统中的目录结构等。
等等。。。
至此，我们已经知道的简单的单链表的基本概念与操作。没错，链表还有更多复杂的分类：双向链表，循环链表，是否带头结点也是重要的一种情形。如下图所示：
其实弄懂了单链表的操作，其他链表的操作基本类似。对于链表的操作，只需要牢记所要操作的节点的当前指针，和前后节点的指针的位置关系，不遗漏，不错指。
小试牛刀
最后附上一道简单的算法题，巩固今天所学：
leetcode , LCR 024. 反转链表
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
