本文介绍: 算法链表是一种用于解决问题的数据结构，它包含了多个节点，每个节点都包含了一个值和一个指向下一个节点的指针。与数组不同，链表的节点在内存中不是连续存储的，而是通过指针链接在一起。通过使用算法链表，可以实现各种常见的算法操作，如插入、删除、查找等。由于链表的特殊结构，插入和删除操作的时间复杂度为O(1)，而查找操作的时间复杂度则为O(n)。链表还可以用来解决一些特殊的问题，比如反转链表、判断链表是否存在环以及找到链表的中间节点等。这些问题在实际开发中经常会遇到，并且链表的特性使得解决方案变得相对简单。
第一关—链表【青铜挑战】
1.1 单链表的概念
解析：第一张图满足单链表的要求，第二张图不满足要求，因为c1它有两个后继结点a5和b4，单链表的核心是一个结点只能有一个后继，但是不代表一个结点只能有一个被指向（如c1可以被a2和b3指向）
注意：做题的时候注意比较的是值还是结点，有时可能两个结点的值是相等的，但并不是同一个结点，例如下图，有两个结点的值都是1，但并不是同一个结点
1.2 链表的相关概念
节点和头节点
虚拟结点
虚拟结点就是一个dummyNode，其next指针指向head头部，也就是
dummyNode.next = head因此，如果我们在算法里使用了虚拟结点，则要注意，如果要获得head结点，或者从方法里返回的时候，则应使用dummyNode.next
另外，dummyNode的val不会被使用，初始化为0或者-1等都是可以的，既然值不会被使用，那么我们就会有疑问？虚拟结点有啥用呢？简单来说，就是为了方便我们处理
头结点，否则我们需要在代码里单独处理头结点【首部结点】的问题
1.3 创建链表 – Java实现
我们首先要理解JVM是怎么构建出链表，JVM里面有栈区和堆区，堆区主要存引用，也就是一个指向实际对象的地址，而堆区存的才是创建的对象
/**
* @Author Zan
* @Date 2023/11/29 14:46
* @Description : 传入一个数组，将其转换成单链表
*/
public class BasicLink {
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6};
Node head = initLinkedList(a);
System.out.println(head);
}
private static Node initLinkedList(int[] array) {
Node head = null, current = null;
for (int i = 0; i < array.length; i++) {
Node newNode = new Node(array[i]);
if (i == 0) { // 头节点
// 由于head = current，因此当current在变化的时候，head也在变化
head = newNode;
// newNode = new Node(array[i]); // 如果在此将newNode重新定义，指向的是不同的堆数据，因此head就只是一个Node普通对象，单节点的链表
current = newNode;
} else { // 后面的节点
current.next = newNode;
current = newNode;
}
}
return head;
}
static class Node {
public int x;
public Node next;
public Node(int x) {
this.x = x;
next = null;
}
}
}
我们可以看到初始化链表的时候，head和current指向的是同一个对象，也就是指向堆中的同一个数据，因此当控制
current.next = newNode的时候，其实就是控制堆中的数据指向谁，next指向下一条数据，而head跟current一样指向的是同一个对象，因此就可以跟随其变化
1.4 链表的增删改查
1.4.1 遍历单链表 – 求单链表长度
/**
* 遍历链表，获取链表的长度
* @param head 头节点
* @return
*/
public static int getListLength(Node head) { // 传入头节点
int length = 0;
Node node = head;
while (node != null) { // 一个一个节点遍历
length++;
node = node.next;
}
return length;
}
1.4.2 链表插入 – 三种位置插入
（1）在链表的表头插入
- 创建新结点newNode
- 新结点的next = head，即
newNode.next = head- 头head指向新的链表，即
head = newNode
/**
* 在链表的表头插入
* @param head 原链表
* @param nodeInsert 要插入表头的结点元素
* @return
*/
public static Node insertNodeByHead(Node head, Node nodeInsert) {
nodeInsert.next = head;
head = nodeInsert;
return head;
}
（2）在链表的中间插入
- 循环找到要插入位置position的前一个结点（位置从1开始）
- 将插入结点的next指向前一个结点的next，即
nodeInsert.next = newNode.next- 将前一个结点的next指向插入结点，即
newNode.next = nodeInsert
- 注意：我们不能先将前一个结点的next指向插入结点，这是因为每个结点都只有一个next，因此如果先将前一个结点的next指向插入结点，那么
15->7这一条线就断掉了，也就导致后面的7、40将会找不到，断开
/**
* 在链表的中间位置插入
* @param head 原链表的头结点
* @param nodeInsert 要插入的结点
* @param position 要插入的位置，从1开始
* @return
*/
public static Node insertNodeByPosition(Node head, Node nodeInsert, int position) {
Node newNode = head; // 不对原链表进行操作，用新链表指向堆中的同一个元素，进行堆中的操作
int i = 1;
while (i < position - 1) { // 要在中间位置插入，因此要获取插入位置的前一个结点，这样子才能将next连接起来
newNode = newNode.next;
i++;
}
nodeInsert.next = newNode.next; // 将要插入的结点的next指向插入位置前一个结点的next
newNode.next = nodeInsert; // 将插入位置前一个结点的next指向要插入的结点
return head;
}
（3）在链表的结尾插入
/**
* 在链表的结尾插入
* @param head 原链表的头结点
* @param nodeInsert 要插入的结点
* @return
*/
public static Node insertByEnd(Node head, Node nodeInsert) {
Node newNode = head;
int nodeLength = getListLength(newNode); // 获取到原链表的元素个数
int i = 1;
while (i < nodeLength) { // 循环遍历找到最后一个结点
newNode = newNode.next;
i++;
}
newNode.next = nodeInsert; // 将最后一个结点的next指向新结点
return head;
}
（4）在链表的所有位置插入[总结]⭐
/**
* 链表的插入（所有情况，表头、中间、结尾）
*
* @param head 原链表
* @param nodeInsert 插入的结点
* @param position 插入的位置，从1开始
* @return
*/
public static Node insertNode(Node head, Node nodeInsert, int position) {
// head原链表中没有数据，插入的结点就是链表的头结点
if (head == null) {
return nodeInsert;
}
// 获取存放元素个数 - 进行校验(position在[1, size]之间)
int size = getListLength(head);
if (position > size + 1 || position < 1) {
System.out.println("位置参数越界");
return head;
}
// 表头插入
if (position == 1) {
nodeInsert.next = head;
head = nodeInsert;
return head;
}
// 中间插入和结尾插入
Node newNode = head;
int count = 1;
while (count < position - 1) {
count++;
newNode = newNode.next;
}
nodeInsert.next = newNode.next;
newNode.next = nodeInsert;
return head;
}
1.4.3 链表删除 – 三种位置删除
（1）删除链表的表头结点
将head表头向前移动一次之后，原先的结点就变成了不可达，会被JVM回收掉
/**
* 删除表头结点
* @param head 原链表
* @return
*/
public static Node deleteByHead(Node head) {
head = head.next;
return head;
}
（2）删除链表的最后一个结点
/**
* 删除最后一个结点
* @param head 原链表
* @return
*/
public static Node deleteByEnd(Node head) {
Node newNode = head;
int size = getListLength(head); // 获取该链表的总长度size
int i = 1;
while (i < size - 1) { // 找到倒数第二个结点
i++;
newNode = newNode.next;
}
newNode.next = null; // 将倒数第二个结点的next指向null
return head;
}
（3）删除链表的中间结点
- 找到要删除结点的前一个结点
- 将前一个结点的next指向下下个结点，即
newNode.next = newNode.next.next
/**
* 删除中间结点
* @param head 原链表
* @return
*/
public static Node deleteByPosition(Node head, int position) {
Node newNode = head;
int i = 1;
while (i < position - 1) {
i++;
newNode = newNode.next;
}
newNode.next = newNode.next.next;
return head;
}
（4）删除链表的任一位置[总结]⭐
/**
* 删除结点（三种情况，表头、中间、最后一位结点）
* @param head 原链表
* @return
*/
public static Node deleteNode(Node head, int position) {
// 如果没有结点，说明无法删除，直接返回null即可
if (head == null) {
return null;
}
//校验
int size = getListLength(head);
if (position > size || position < 1) { // 这里不是size+1，而插入是size+1，因为插入可以插入到最后一位（未知的最后一位），而删除必须要是已知的，不能是未知的越界
System.out.println("输入的参数有误");
return head;
}
if (position == 1) { // 删除头节点
return head.next;
} else { // 删除中间结点或者最后一个结点
Node newNode = head;
int count = 1;
while (count < position - 1) {
count++;
newNode = newNode.next;
}
newNode.next = newNode.next.next;
return head;
}
}
原文地址:https://blog.csdn.net/weixin_65508929/article/details/134699742
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_11851.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
