数据结构：顺序表与链表经典算法实战

链表算法（指针操作）

移除链表元素

不需要真的创建新链表，通过修改指针指向即可。注意处理头节点可能就是要删除的情况，使用哨兵位能简化逻辑。

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode dummy = {0};
    dummy.next = head;
    struct ListNode* cur = &dummy;
    
    while (cur->next) {
        if (cur->next->val == val) {
            struct ListNode* tmp = cur->next;
            cur->next = tmp->next;
            free(tmp);
        } else {
            cur = cur->next;
        }
    }
    return dummy.next;
}

反转链表

有两种主流写法：头插法和三指针法。头插法直观但容易忘断尾；三指针法原地反转更节省空间。

// 三指针法
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    struct ListNode* next = NULL;
    
    while (curr) {
        next = curr->next;      // 暂存下一个
        curr->next = prev;      // 反转指针
        prev = curr;            // 移动 prev
        curr = next;            // 移动 curr
    }
    return prev;
}

关键点：循环结束后 prev 就是新头，记得把旧头节点的 next 置为 NULL，防止成环。

链表的中间节点

快慢指针的经典应用。快指针每次走两步，慢指针走一步。当快指针到头时，慢指针正好在中间。

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

注意短路求值，fast->next 判空在前，避免空指针解引用。

合并两个有序链表

同样推荐用哨兵位。比较两个链表当前节点的值，小的接在尾后，最后把非空的那段拼上去。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy = {0};
    struct ListNode* tail = &dummy;
    
    while (list1 && list2) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    tail->next = list1 ? list1 : list2;
    return dummy.next;
}

链表分割

类似归并排序的思想，维护两个子链表（小于 x 和大于等于 x），最后拼接。同样使用哨兵位减少边界判断。

struct ListNode* partition(struct ListNode* pHead, int x) {
    struct ListNode lessDummy = {0}, greatDummy = {0};
    struct ListNode* lessTail = &lessDummy;
    struct ListNode* greatTail = &greatDummy;
    struct ListNode* cur = pHead;
    
    while (cur) {
        if (cur->val < x) {
            lessTail->next = cur;
            lessTail = cur;
        } else {
            greatTail->next = cur;
            greatTail = cur;
        }
        cur = cur->next;
    }
    greatTail->next = NULL; // 断开连接，防止成环
    lessTail->next = greatDummy.next;
    return lessDummy.next;
}

链表的回文结构

方法一：转数组再判断，空间 O(N)。方法二：找中点 -> 反转后半段 -> 对比。推荐后者，空间 O(1)。

bool chkPalindrome(struct ListNode* A) {
    struct ListNode* mid = middleNode(A);
    struct ListNode* right = reverseList(mid); // 反转后半段
    struct ListNode* left = A;
    
    while (right) {
        if (left->val != right->val) return false;
        left = left->next;
        right = right->next;
    }
    return true;
}

相交链表

计算两链表长度差，长链表先走差值步，然后同步遍历。或者用更巧妙的'互相走完对方路径'的方法，这里展示通用的长度差法。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    int sizeA = 0, sizeB = 0;
    struct ListNode* pa = headA, *pb = headB;
    while (pa) { sizeA++; pa = pa->next; }
    while (pb) { sizeB++; pb = pb->next; }
    
    struct ListNode* longList = headA, *shortList = headB;
    int gap = sizeA - sizeB;
    if (sizeA < sizeB) {
        longList = headB; shortList = headA;
        gap = sizeB - sizeA;
    }
    
    while (gap--) longList = longList->next;
    while (longList && shortList) {
        if (longList == shortList) return longList;
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}

环形链表检测

判断是否有环

快慢指针，快指针每次走两步，慢指针走一步。如果在环内，快指针迟早会追上慢指针。

bool hasCycle(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

为什么快指针走三步不行？因为如果环长是偶数且距离差是奇数，可能会错过。走两步能保证相对速度为 1，最终必相遇。

寻找入环节点

相遇后，让一个指针从头开始，另一个从相遇点继续走，每次一步。再次相遇的点即为入口。数学推导证明两者距离相等。

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return NULL;
    
    struct ListNode* ptr1 = head, *ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return ptr1;
}

以上算法涵盖了线性结构中最核心的操作模式。掌握这些模板，面对变体题也能快速拆解。