链表相关算法

查找链表 倒数第n个节点：

WX20201014-190534.png

// 链表节点定义
struct Node {
    // 数据
    int data;
    // 下一个指针
    struct Node * _Nullable next;
};


// 整数数组转单链表
struct Node * arrayToList(int datas[_Nonnull], int length) {
    // 头结点
    struct Node *head = NULL;
    // 尾结点
    struct Node *tail = NULL;
    
    // 将数组中的每一个值作为结点的数据
    for (int i = 0; i < length; i++) {
        // 创建节点
        struct Node *node = malloc(sizeof(struct Node));
        node->data = datas[i];
        node->next = NULL;
        
        // 新节点加到链表末尾
        if (NULL == head) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = tail->next;
        }
    }
    
    // 返回头结点
    return head;
}


// 反转链表
struct Node * reverseList(struct Node *head) {
    struct Node *previous = NULL;
    struct Node *current = head;
    struct Node *next = NULL;
    
    // 反转
    while (NULL != current) {
        // 1. 将下一个保存在`next`中。
        next = current->next;
        // 2. 反转：将下一个指向前一个。
        current->next = previous;
        // 3. 移动：前一个移动到当前。
        previous = current;
        // 4. 移动：当前移动到下一个。
        current = next;
    }
    
    // current已经移动到最后，previous就是新的头
    return previous;
}