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

合并两个有序数组

思路： 从后往前遍历。比较 nums1 和 nums2 的末尾元素，将较大的放入 nums1 的末尾位置。这样可以避免覆盖 nums1 中尚未处理的元素。若 nums2 还有剩余，需继续拷贝到 nums1 头部。

• 时间复杂度： O(N)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;
    while (l1 >= 0 && l2 >= 0) {
        if (nums1[l1] > nums2[l2]) {
            nums1[l3--] = nums1[l1--];
        } else {
            nums1[l3--] = nums2[l2--];
        }
    }
    while (l2 >= 0) {
        nums1[l3--] = nums2[l2--];
    }
}

链表算法（快慢指针、三指针、哨兵位）

移除链表元素

思路： 创建虚拟头结点（哨兵位），简化空链表判断。遍历原链表，将值不等于 val 的节点尾插到新链表中。最后记得断开尾节点的 next 指针，防止成环。

• 时间复杂度： O(N)
• 空间复杂度： O(1)

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

反转链表

思路： 提供两种方法。

1. 头插法： 遍历原链表，将每个节点插入到新链表头部。需注意保存下一个节点，并将原头节点置为 NULL。
2. 三指针法： 使用 prev, curr, next 三个指针原地修改指向。curr->next 指向 prev，然后三者同步移动。

• 时间复杂度： O(N)
• 空间复杂度： O(1)

// 三指针法
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

链表的中间节点

思路： 快慢指针。slow 每次走一步，fast 每次走两步。当 fast 到达末尾时，slow 恰好位于中间。注意短路求值防止空指针解引用。

• 时间复杂度： O(N)

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;
}

合并两个有序链表

思路： 同样使用哨兵位简化逻辑。比较两个链表当前节点的值，将较小的节点连接到结果链表尾部。任一链表遍历结束后，将另一链表剩余部分直接接上。

• 时间复杂度： O(N)

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

链表分割

思路： 创建两个带哨兵位的链表（小于 x 和大等于 x）。遍历原链表，根据节点值分别尾插到两个子链表中。最后连接两个子链表，注意大链表尾部置空。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode lessDummy = {0}, greatDummy = {0};
        ListNode* lessTail = &lessDummy;
        ListNode* greatTail = &greatDummy;
        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;
    }
};

链表的回文结构

思路： 结合前面讲过的'找中间节点'和'反转链表'。找到中点后，反转后半部分链表，然后从头和中点开始同步遍历比较节点值。若全部相等则为回文。

bool chkPalindrome(ListNode* A) {
    if (!A || !A->next) return true;
    
    // 1. 找中间节点
    ListNode* slow = A, *fast = A;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 2. 反转后半部分
    ListNode* prev = NULL, *curr = slow;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    // 3. 比较
    ListNode* left = A;
    ListNode* right = prev;
    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 lenA = 0, lenB = 0;
    struct ListNode* pa = headA, *pb = headB;
    
    while (pa) { lenA++; pa = pa->next; }
    while (pb) { lenB++; pb = pb->next; }
    
    int gap = abs(lenA - lenB);
    struct ListNode* longList = lenA > lenB ? headA : headB;
    struct ListNode* shortList = lenA > lenB ? headB : headA;
    
    while (gap--) longList = longList->next;
    
    while (longList && shortList) {
        if (longList == shortList) return longList;
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}

环形链表（快慢指针）

环形链表 I

思路： 快慢指针进入环后，由于速度差为 1，最终一定会相遇。若快指针能追上慢指针，则说明存在环。

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;
}

环形链表 II

思路： 当快慢指针在环内相遇后，将一个指针重置到头结点，另一个保持在相遇点。两者每次各走一步，再次相遇的点即为入环点。原理基于数学推导：头结点到入环点的距离等于相遇点到入环点的距离。

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;
    
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

注： 关于快指针每次走三步是否可行？理论上只要步长与慢指针互质且满足特定数学条件，最终也能相遇，但标准 Floyd 算法采用步长 2 最为稳妥高效。