编程导航算法通关村第 1 关 | 链表

标签：head ListNode 编程 next 链表 n0 节点通关

1. 前置知识补充

内容引用:https://www.hello-algo.com/

数据结构

数据结构如同一副稳固而多样的框架。

它为数据的有序组织提供了蓝图，使算法得以在此基础上生动起来。

2. 链表

「链表 linked list」是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

2.1 链表的定义

/* 链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向下一节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

2.2 单链表的操作

1. 初始化链表

建立链表分为两步，第一步是初始化各个节点对象，第二步是构建引用指向关系。初始化完成后，我们就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点。

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// 构建引用指向
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

2. 插入节点

在链表中插入节点非常容易。如图 4-6 所示，假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需要改变两个节点引用（指针）即可，时间复杂度为 O(1) 。

相比之下，在数组中插入元素的时间复杂度为 O(n) ,在大数据量下的效率较低。

链表插入节点示例

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

3. 删除节点

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

请注意，尽管在删除操作完成后节点 P 仍然指向 n1 ，但实际上遍历此链表已经无法访问到 P ，这意味着 P 已经不再属于该链表了。

链表删除节点

/* 删除链表的节点 n0 之后的首个节点 */
void remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}

4. 访问节点

在链表访问节点的效率较低。我们可以在O(1) 时间下访问数组中的任意元素。链表则不然，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第 i 个节点需要循环 i −1 轮，时间复杂度为 O(n) 。

PythonC++JavaC#GoSwiftJSTSDartRustCZig

linked_list.java

/* 访问链表中索引为 index 的节点 */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

5. 查找节点

遍历链表，查找链表内值为 target 的节点，输出节点在链表中的索引。此过程也属于线性查找。

/* 在链表中查找值为 target 的首个节点 */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

3. 问题

1.链表增加元素，首部、中间和尾部分别会有什么问题，该如何处理？

首部
- 问题：在链表的首部添加元素可能导致原来的首节点被替换，从而丢失对原始首节点的引用。
- 处理方法：可以创建一个新的节点，并将其设置为新的首节点。新节点的下一个节点将指向原始首节点，从而保留对原始首节点的引用。(将新的头部和原有头部分开保存)
- 问题: 经常会忘了head需要重新指向表头
- 解决方法: 将head重新指向newNode
中间
- 问题：在链表的中间位置添加元素会涉及节点的重新连接，需要确保插入节点的前一个节点和后一个节点正确连接，否则会导致数据丢失或链表断裂。
- 处理方法：可以按照以下步骤处理中间添加元素：
  - 创建一个新节点，并将要插入的元素存储在新节点中。
  - 找到要插入的位置的前一个节点。
  - 将新节点的下一个节点设置为前一个节点的下一个节点。
  - 将前一个节点的下一个节点设置为新节点。

标签：head,ListNode,编程,next,链表,n0,节点,通关
From： https://www.cnblogs.com/ks2022/p/17781362.html