【程序员面试高频算法】一篇文章搞定链表，附C语言源码，建议收藏！

一个程序员对计算机底层原理的理解，决定了他职业生涯的上限。
图片

单链表是面试中频繁考察的重点之一。

今天，我们就来深入剖析单链表，涵盖其定义、特点、优缺点、适用场景，以及一系列高频算法题（增删改查、翻转、找倒数第k个节点、判断是否有环等）的解法，并附上C语言源码，让你轻松掌握这一关键知识点。
‌单链表的定义‌

单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。这种结构通过指针将各个节点连接起来，形成一条链。

‌单链表的特点‌
动态性：链表长度不固定，可随需求增加或减少节点。

节点不连续：链表节点在内存中无需连续存储，有助于内存利用。

‌单链表的优缺点‌
优点

插入和删除操作高效，特别是在链表头部或中间位置。

适用于元素数量不固定的动态场景。

缺点

查询效率低，无法直接通过索引访问元素，需从头节点顺序遍历。
‌单链表的使用场景‌
链表是非常重要的数据结构，应用场景广泛。

适用于实现栈、队列、树等复杂数据结构。

在需要频繁插入和删除操作的场景中表现出色，如动态数据集合、缓存淘汰策略等。

相较于数组，链表在处理元素动态变化的场景时更具优势；但在频繁查询元素的场景中，数组更为合适。

单链表因其动态性和灵活性，在处理元素不固定且需要频繁插入、删除的场景中具有重要的应用价值。

代码实现

一、数据结构定义

// 定义单链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 定义单链表结构体（包含头节点）
typedef struct LinkedList {
    ListNode* head;
} LinkedList;

// 创建一个新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 创建一个空链表
LinkedList* createLinkedList() {
    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = NULL;
    return list;
}

二、增删改查操作
插入操作

1. 头部插入

// 在链表头部插入新节点
void insertAtHead(LinkedList* list, int val) {
    ListNode* newNode = createNode(val);
    newNode->next = list->head;
    list->head = newNode;
}

2. 中间插入

// 在指定位置（假设位置从1开始计数）之后插入新节点
void insertAfterPosition(LinkedList* list, int position, int val) {
    ListNode* newNode = createNode(val);
    ListNode* current = list->head;
    int count = 1;
    while (current!= NULL && count < position) {
        current = current->next;
        count++;
    }
    if (current!= NULL) {
        newNode->next = current->next;
        current->next = newNode;
    } else {
        printf("Position out of range.\n");
    }
}

3. 尾部插入

// 在链表尾部插入新节点
void insertAtTail(LinkedList* list, int val) {
    ListNode* newNode = createNode(val);
    if (list->head == NULL) {
        list->head = newNode;
        return;
    }
    ListNode* current = list->head;
    while (current->next!= NULL) {
        current = current->next;
    }
    current->next = newNode;
}

删除操作

1. 删除头部节点

// 删除链表头部节点
void deleteHead(LinkedList* list) {
    if (list->head!= NULL) {
        ListNode* temp = list->head;
        list->head = list->head->next;
        free(temp);
    } else {
        printf("List is empty.\n");
    }
}

2. 删除中间节点

// 删除指定位置（假设位置从1开始计数）的节点
void deleteAtPosition(LinkedList* list, int position) {
    ListNode* current = list->head;
    ListNode* prev = NULL;
    int count = 1;
    while (current!= NULL && count < position) {
        prev = current;
        current = current->next;
        count++;
    }
    if (current!= NULL) {
        if (prev == NULL) {
            list->head = current->next;
        } else {
            prev->next = current->next;
        }
        free(current);
    } else {
        printf("Position out of range.\n");
    }
}

3. 删除尾部节点

// 删除链表尾部节点
void deleteTail(LinkedList* list) {
    if (list->head == NULL) {
        printf("List is empty.\n");
        return;
    }
    ListNode* current = list->head;
    ListNode* prev = NULL;
    while (current->next!= NULL) {
        prev = current;
        current = current->next;
    }
    if (prev == NULL) {
        list->head = NULL;
    } else {
        prev->next = NULL;
    }
    free(current);
}

查询操作

// 查询链表中是否存在指定值
int searchList(LinkedList* list, int val) {
    ListNode* current = list->head;
    while (current!= NULL) {
        if (current->val == val) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

修改操作

// 修改指定位置（假设位置从1开始计数）节点的值
void modifyAtPosition(LinkedList* list, int position, int newVal) {
    ListNode* current = list->head;
    int count = 1;
    while (current!= NULL && count < position) {
        current = current->next;
        count++;
    }
    if (current!= NULL) {
        current->val = newVal;
    } else {
        printf("Position out of range.\n");
    }
}

三、算法进阶

翻转链表

// 翻转单链表
ListNode* reverseList(LinkedList* list) {
    ListNode* prev = NULL;
    ListNode* current = list->head;
    ListNode* next = NULL;
    while (current!= NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    list->head = prev;
    return list->head;
}

找链表的倒数第 k 个节点

// 找到单链表的倒数第 k 个节点
ListNode* findKthFromEnd(LinkedList* list, int k) {
    ListNode* slow = list->head;
    ListNode* fast = list->head;
    // 让快指针先走 k 步
    for (int i = 0; i < k; i++) {
        if (fast == NULL) {
            printf("k is larger than the length of the list.\n");
            return NULL;
        }
        fast = fast->next;
    }
    // 然后慢指针和快指针一起走，当快指针走到链表末尾时，慢指针就是倒数第 k 个节点
    while (fast!= NULL) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

判断单链表是否有环

// 判断单链表是否有环
int hasCycle(LinkedList* list) {
    ListNode* slow = list->head;
    ListNode* fast = list->head;
    while (fast!= NULL && fast->next!= NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return 1; // 有环
        }
    }
    return 0; // 无环
}

希望这篇文章能对你有所帮助，记得收藏起来哦，方便随时查阅和复习。