一. 链表的定义
链表是一种线性数据结构，由一系列节点组成。每个节点包含两个部分：
- 数据域（Data）：存储节点的数据。
- 指针域（Pointer）：存储指向下一个节点的地址。
链表的第一个节点称为头节点（Head），最后一个节点的指针域指向空（NULL），表示链表的结束。
二. 链表的结构
1) 单向 / 双向
2) 带头 / 不带头
3) 循环 / 非循环
链表种类丰富多样 重点掌握 单向不带头非循环 链表 可作为其他数据结构的子结构，如 哈希桶、图的邻接表等 笔试常考
三. 实现链表
1) 节点类：
定义链表节点类，每个节点包含数据和指向下一个节点的指针。
public class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}
}
2) 链表类:
用于实现链表的功能
public class MySingleList {private ListNode head;static class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;this.next = null;}}public ListNode cur; // 临时头节点
}插入节点:
插入节点 图示
// 在链表的末尾插入一个新节点void append(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;} else {Node current = head;while (current.next != null) {current = current.next;}current.next = newNode;}usedSize++;}// 在链表的开头插入一个新节点void prepend(int data) {Node newNode = new Node(data);newNode.next = head;head = newNode;usedSize++;}// 在指定位置插入一个新节点void insertAt(int index, int data) {if (index < 0 || index > usedSize) {throw new IndexOutOfBoundsException("Index out of bounds");}Node newNode = new Node(data);if (index == 0) {newNode.next = head;head = newNode;} else {Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}newNode.next = current.next;current.next = newNode;}usedSize++;}删除节点:
// 删除指定位置的节点void deleteAt(int index) {if (index < 0 || index >= usedSize) {throw new IndexOutOfBoundsException("Index out of bounds");}if (index == 0) {head = head.next;} else {Node current = head;for (int i = 0; i < index - 1; i++) {current = current.next;}current.next = current.next.next;}usedSize--;}查找节点:
// 查询指定位置的节点Node getNodeAt(int index) {if (index < 0 || index >= usedSize) {throw new IndexOutOfBoundsException("Index out of bounds");}Node current = head;for (int i = 0; i < index; i++) {current = current.next;}return current;}四. 链表OJ 实战 !
1) 开胃小菜 删除所有值域为val的节点
力扣链接: . - 力扣（LeetCode）
class Solution {public ListNode removeElements(ListNode head, int val) {while(head!= null && head.val == val){head = head.next;}ListNode cur = head;while(cur != null && cur.next != null){if(cur.next.val == val){cur.next = cur.next.next;}else{cur = cur.next;}}return head;}
}2) 反转链表 重要程度 五颗星 !!!
力扣链接: . - 力扣（LeetCode）
// 反转链表public ListNode reverseList(ListNode head) {// 定义两个指针，pre初始化为null，用于存储反转后的链表ListNode pre = null;// cur初始化为head，表示当前处理的节点ListNode cur = head;// 循环直到cur为null，表示已经处理完所有节点while(cur != null){// temp临时存储cur的下一个节点，因为接下来要修改cur.nextListNode temp = cur.next;// 将cur的next指针指向pre，实现反转cur.next = pre;// pre和cur都前进一步pre = cur; // pre移动到cur的位置cur = temp; // cur移动到下一个待处理的节点}// 当cur为null时，pre就是新链表的头节点return pre;}思路: 在遍历链表时逐步反转每个节点的指针方向
3) 快慢指针算法
快慢指针: 处理环形链表或数组非常有用
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
力扣链接: 876. 链表的中间结点 - 力扣（LeetCode）
public ListNode middleNode(ListNode head) {// 定义快慢指针，都初始化为头节点headListNode fast = head;ListNode slow = head;// 循环条件，快指针fast及其next不为nullwhile (fast != null && fast.next != null) {// 快指针fast每次向前移动两步fast = fast.next.next;// 慢指针slow每次向前移动一步slow = slow.next;}// 当快指针到达链表末尾时，慢指针正好到达中间节点return slow;}原理 : 因为fast的速度是 slow的速度的二倍, 而fast走完,slow 必然在中间位置.
4) 合并两个有序链表:
思路 : 使用 虚拟节点 为了简化头节点的处理逻辑
比较大小 插入新链表
如果其中一个链表的节点全部被插入到新链表中，如果另一个链表还有剩余节点， 直 接将这些剩余节点链接到新链表的末尾。
记得最后返回虚拟节点的下一个节点.
力扣链接: . - 力扣（LeetCode）
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dummy = new ListNode(-1);//虚拟节点// 创建一个指针cur，用来遍历并构建新的合并后的链表，初始指向哑节点ListNode cur = dummy;// 遍历链表直到其中一个为空while(list1 != null && list2 != null){if(list1.val > list2.val){cur.next = list2;list2 = list2.next;}else{cur.next = list1;list1 = list1.next;}cur = cur.next;}// 如果其中一个链表先遍历完，将另一个链表的剩余部分连接到新链表的末尾cur.next = (list1 == null) ? list2:list1;return dummy.next; //返回虚拟节点的下一个节点}五. ArrayList和LinkedList的区别
- 数组: 适用于需要快速访问和固定大小的情况。
- 链表: 适用于频繁插入和删除、且大小动态变化的情况。
六. 总结
链表作为数据结构中的佼佼者，凸显了其在动态数据操作场景下的独特价值，特别是对于需要频繁执行插入和删除操作的应用来说，更是不可或缺。掌握链表的基础操作，包括但不限于节点的创建、插入、删除及遍历，以及进阶技巧如链表的反转、合并操作，以及利用快慢指针解决复杂链表问题，是深化链表理解和应用实践的关键步骤。在链表与数组的权衡选择上，认识到两者各自的强项——数组的快速随机访问与链表的高效动态修改能力，是根据具体需求制定数据结构策略的先决条件。总而言之，链表的灵活高效使其在众多计算领域内占有一席之地，而深入探索其特性和应用，则是对每一位技术探索者的智慧挑战与能力提升之旅。
