单向链表六大核心操作详解：销毁、查找、倒置与排序

销毁时需暂存下一个节点地址，传入头指针的地址以便将头节点设为 NULL。

三、查找中间节点

常用快慢指针法。快指针每次走 2 步，慢指针每次走 1 步，快指针到尾时，慢指针在中点。

Node* findMiddleNode(Node* head) {
    if (head == NULL || head->next == NULL) return head;
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

偶数长度时返回第一个中间节点。若需返回靠后的中间节点，可调整初始条件。

四、查找倒数第 K 个节点

双指针法。先让指针 p1 走 K 步，再 p1 和 p2 同步走，p1 到尾时 p2 为倒数第 K 个。

Node* findKthFromEnd(Node* head, int k) {
    if (head == NULL || k <= 0) return NULL;
    Node* p1 = head;
    Node* p2 = head;
    for (int i = 0; i < k; i++) {
        if (p1 == NULL) return NULL;
        p1 = p1->next;
    }
    while (p1 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p2;
}

需注意 K 的合法性（K<=0 或 K>链表长度）。

五、链表的倒置

将链表方向反转，如 1->2->3 变为 3->2->1。常用迭代法（三指针）。

Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* curr = head;
    Node* next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

时间复杂度 O(n)，空间 O(1)。递归法也可实现但易栈溢出。

六、链表的排序（冒泡与选择）

1. 冒泡排序

相邻节点比较交换，每轮将最大节点沉底。

void bubbleSortList(Node* head) {
    if (head == NULL || head->next == NULL) return;
    int swapped;
    Node* ptr;
    Node* last = NULL;
    do {
        swapped = 0;
        ptr = head;
        while (ptr->next != last) {
            if (ptr->data > ptr->next->data) {
                int temp = ptr->data;
                ptr->data = ptr->next->data;
                ptr->next->data = temp;
                swapped = 1;
            }
            ptr = ptr->next;
        }
        last = ptr;
    } while (swapped);
}

2. 选择排序

每轮找最小节点，与当前位置交换。

void selectionSortList(Node* head) {
    if (head == NULL || head->next == NULL) return;
    Node* curr = head;
    while (curr != NULL && curr->next != NULL) {
        Node* minNode = curr;
        Node* temp = curr->next;
        while (temp != NULL) {
            if (temp->data < minNode->data) minNode = temp;
            temp = temp->next;
        }
        if (minNode != curr) {
            int tempData = curr->data;
            curr->data = minNode->data;
            minNode->data = tempData;
        }
        curr = curr->next;
    }
}

链表排序可直接交换数据（简单）或交换节点（复杂）。

七、判断链表是否有环

快慢指针法。快指针每次 2 步，慢指针每次 1 步，相遇则有环。

int hasCycle(Node* head) {
    if (head == NULL || head->next == NULL) return 0;
    Node* slow = head;
    Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

若有环，快指针会追上慢指针；若无环，快指针先到尾。时间复杂度 O(n)，空间 O(1)。

总结

单向链表核心操作围绕指针 manipulation 展开。销毁释放内存，快慢指针解决中间/倒数第 K/环检测，迭代反转链表，冒泡选择排序链表。掌握这些操作需理解指针指向变化，多画图模拟过程，结合实际示例调试代码，方能融会贯通。链表是更复杂结构的基础，务必扎实掌握。