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

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

// 删除有序数组中的重复项
int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int src = 1, dst = 0;
    while (src < numsSize) {
        if (nums[src] != nums[dst]) {
            dst++;
            nums[dst] = nums[src];
        }
        src++;
    }
    return dst + 1;
}

合并两个有序数组

题目链接

思路解析： 为了避免覆盖 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--];
        }
    }
    // 若 nums2 还有剩余，需拷贝到 nums1
    while (l2 >= 0) {
        nums1[l3--] = nums2[l2--];
    }
}

链表算法题（快慢指针，三指针法）

移除链表元素

题目链接

思路解析： 虽然题目看似创建新链表，实际是通过修改原链表指针来实现。我们维护一个虚拟头节点或新的尾指针，将不为 val 的节点依次尾插到新链表中。注意最后要将新尾节点的 next 置为 NULL，防止形成环。

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

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode newHead;
    struct ListNode* tail = &newHead;
    struct ListNode* pcur = head;
    
    while (pcur) {
        if (pcur->val != val) {
            tail->next = pcur;
            tail = pcur;
        }
        pcur = pcur->next;
    }
    tail->next = NULL;
    return newHead.next;
}

反转链表

题目链接

思路解析： 提供两种常见解法。

1. 头插法：遍历原链表，将节点依次插入到新链表头部。需注意保存下一个节点，并将原头节点置空以防成环。
2. 三指针法：使用 prev, curr, next 三个指针，原地改变指针指向。这是最节省空间的写法。

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

// 方法一：头插法
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newHead = NULL;
    struct ListNode* pcur = head;
    while (pcur) {
        struct ListNode* next = pcur->next;
        pcur->next = newHead;
        newHead = pcur;
        pcur = next;
    }
    return newHead;
}

// 方法二：三指针法
struct ListNode* reverseList_v2(struct ListNode* head) {
    if (!head) return NULL;
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    struct ListNode* next = curr->next;
    while (curr) {
        curr->next = prev;
        prev = curr;
        curr = next;
        if (next) next = next->next;
    }
    return prev;
}

链表的中间节点

题目链接

思路解析： 经典的快慢指针应用。慢指针每次走一步，快指针每次走两步。当快指针到达终点时，慢指针恰好位于中间。

时间复杂度：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;
}

合并两个有序链表

题目链接

思路解析： 遍历两个链表，比较节点值，将较小的节点尾插到新链表中。为了简化边界判断，可以使用哨兵节点（Dummy Node），最后返回哨兵的 next 即可。

时间复杂度：O(N)。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    struct ListNode* l1 = list1;
    struct ListNode* l2 = list2;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

链表分割

题目链接

思路解析： 创建两个带哨兵位的链表，分别存储小于 x 和大于等于 x 的节点。遍历原链表进行分流，最后将小链表与大链表首尾相连。记得断开大链表尾部以防成环。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode lessHead, *lessTail = &lessHead;
        ListNode greatHead, *greatTail = &greatHead;
        ListNode* pcur = pHead;

        while (pcur) {
            if (pcur->val < x) {
                lessTail->next = pcur;
                lessTail = pcur;
            } else {
                greatTail->next = pcur;
                greatTail = pcur;
            }
            pcur = pcur->next;
        }
        greatTail->next = NULL;
        lessTail->next = greatHead.next;
        return lessHead.next;
    }
};

链表的回文结构

题目链接

思路解析：

1. 数组法：遍历链表存入数组，用双指针判断数组是否为回文。空间复杂度 O(N)。
2. 反转法：找到中间节点，反转后半部分链表，然后同时遍历前后两部分比较。空间复杂度 O(1)。

class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    struct ListNode* reverseList(struct ListNode* head) {
        if (!head) return NULL;
        struct ListNode* prev = NULL, *curr = head, *next = curr->next;
        while (curr) {
            curr->next = prev;
            prev = curr;
            curr = next;
            if (next) next = next->next;
        }
        return prev;
    }

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

相交链表

题目链接

思路解析： 计算两个链表的长度，让长链表先走差值步，使两链表尾部对齐，然后同步遍历。若存在交点，必在尾部相遇。另一种更巧妙的方法是双指针交换路径，最终会在交点或 NULL 处相遇。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* pa = headA, *pb = headB;
    int sizeA = 0, sizeB = 0;
    while (pa) { ++sizeA; pa = pa->next; }
    while (pb) { ++sizeB; pb = pb->next; }

    struct ListNode* shortList = headA, *longList = headB;
    if (sizeA > sizeB) { longList = headA; shortList = headB; }

    int gap = abs(sizeA - sizeB);
    while (gap--) longList = longList->next;

    while (shortList && longList) {
        if (shortList == longList) return shortList;
        shortList = shortList->next;
        longList = longList->next;
    }
    return NULL;
}

环形链表（快慢指针）

环形链表 I

题目链接

思路解析： 快慢指针，慢指针每次走一步，快指针每次走两步。如果链表有环，快指针终将追上慢指针。

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

思考：为什么快指针每次走两步，慢指针走一步一定会相遇？ 假设环长度为 C，入环前距离为 L。当慢指针进入环时，快指针已在环内。两者相对速度为 1，只要环内距离有限，快指针必然能追上慢指针。即使快指针一次走 3 步或更多，只要步长与 1 互质，最终也能相遇。

环形链表 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;

    struct ListNode* pcur = head;
    while (pcur != slow) {
        pcur = pcur->next;
        slow = slow->next;
    }
    return pcur;
}

数学证明简述： 设头到入口距离为 L，入口到相遇点距离为 X，环长为 R。快指针路程是慢指针两倍：2(L+X) = L+X+nR。化简得 L = nR - X。这意味着从头走 L 步与从相遇点走 L 步（即 nR-X）会到达同一点（入口）。