链表基础概念及常用算法题解析

链表的概念以及结构

概念：链表是一种物理存储结构上不连续的、非顺序的存储结构，数据元素的顺序是通过节点中的指针来实现的。

结构：（此处指单向非循环链表）链表中每个节点的存储元素一般包含两部分，数据和下一个节点的地址。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

![链表结构示意图]

遍历打印链表

在链表中访问元素需要通过每个节点中存放的下一个元素地址，才能找到下一个节点的位置。具体代码实现如下：

// 遍历链表
void SListPrint(SListNode* phead) {
    SListNode* cur = phead; // 创建一个指针来指向头结点的位置
    while(cur) {
        printf("%d->", cur->val); // 打印当前节点的数据
        cur = cur->next; // 将指针指向下一个节点
    }
}

申请节点

链表中每一个节点都是动态开辟出来的，所以要新增一个节点之前要先申请一个节点，每个节点的大小为该结构体的大小，开辟成功之后，该节点数据部分存放输入的值，地址（next）置为 NULL。

C 语言代码展示如下（这部分主要是为了了解具体实现步骤）：

// 申请节点
SListNode* SListBuyNode(SListNodeDataType x) {
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 申请地址空间
    if (newnode == NULL) { // 判断是否成功
        perror("malloc:");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

用 C++ 则更为简洁且更加安全，代码如下：

struct  {
     val;
    ListNode* next;
    ( x) : (x), () {};
};

ListNode* newNode =  (newValue);