数据结构：顺序表与链表核心算法实战

顺序表算法题（双指针法）

移除元素

题目链接：LeetCode - 移除元素

这道题是双指针法的经典入门。思路很简单：创建两个变量 src 和 dst，src 负责探路，寻找非目标值的元素；dst 负责站岗，记录有效数据的位置。

当 src 指向的数据不等于 val 时，将其赋值给 dst 位置，然后 dst 前进一步；无论是否赋值，src 都要前进一步。最终 dst 的值即为新数组的长度。

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

// 移除元素
int removeElement(int* nums, int numsSize, int val){
    // 创建两个变量
    int src = 0, dst = 0;
    while(src < numsSize){
        // src 指向的数据不是 val，赋值并移动 dst
        if(nums[src] != val){
            nums[dst] = nums[src];
            dst++;
        }
        src++;
    }
    return dst;
}

删除有序数组中的重复项

题目链接：LeetCode - 删除有序数组中的重复项

同样是双指针法，但这里利用了数组有序的特性。src 指向当前检查的元素，dst 指向已去重部分的末尾。

如果 src 和 dst 指向的值不同，说明遇到了新元素，将 dst 后移并赋值；如果相同则跳过。注意优化点：如果 ++dst == src，意味着自己给自己赋值，可以跳过。

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

// 删除有序数组中的重复项
int removeDuplicates(int* nums, int numsSize){
    // 创建两个变量，分别指向数组起始和下一个位置
    int src = 1, dst = 0;
    while(src < numsSize){
        // 优化：避免自己给自己赋值
        if(nums[src] != nums[dst] && ++dst != src){
            nums[dst] = nums[src];
        }
        src++;
    }
    return dst + 1;
}

合并两个有序数组

题目链接：LeetCode - 合并两个有序数组

这道题如果从前往后合并，需要频繁移动元素，效率低。更好的策略是从后往前遍历，比较谁大谁先放后面，这样不需要额外空间。

时间复杂度：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--];
        }
    }
    // l1 越界（不需要特殊处理，nums1 剩余部分已在原位）
    // l2 越界（需要特殊处理，把 nums2 剩余部分拷贝过去）
    while(l2 >= 0){
        nums1[l3--] = nums2[l2--];
    }
}

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

移除链表元素

题目链接：LeetCode - 移除链表元素

思路是通过尾插法构建一个新链表，只保留值不为 val 的节点。这里所谓的'创建新链表'，实际上是通过修改原链表的指针连接实现的，不需要额外开辟节点内存。

需要注意最后一定要把新尾节点的 next 置为 NULL，否则会把剩余的无效节点带过来形成环或垃圾数据。

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

// 移除链表元素
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){
    ListNode* newHead, *newTail;
    newHead = newTail = NULL;
    ListNode* pcur = head;
    while(pcur){
        // 判断 pcur 节点的值是否为 val
        if(pcur->val != val){
            // 尾插，分类讨论链表是否为空
            if(newHead == NULL){
                newHead = newTail = pcur;
            } else {
                newTail->next = pcur;
                newTail = pcur;
            }
        }
        pcur = pcur->next;
    }
    // 最后别忘了把尾节点的 next 置为空，不然会把剩下的节点带过来
    if(newTail){
        newTail->next = NULL;
    }
    return newHead;
}

反转链表

题目链接：LeetCode - 反转链表

有两种常见思路：一是头插法，二是三指针法。

头插法虽然直观，但容易忽略保存下一个节点导致断链。三指针法更稳健，通过 n1, n2, n3 三个指针逐步改变指向。

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

// 方法一：头插法
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    ListNode* pcur = head;
    ListNode* newHead = head;
    while(pcur){
        // 头插
        ListNode* next = pcur->next; // 保存下一个节点
        pcur->next = newHead;
        newHead = pcur;
        pcur = next;
    }
    if(head) // 注意尾节点，避免成环
        head->next = NULL;
    return newHead;
}

// 方法二：三指针法（推荐）
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL) // 需要处理一下特殊情况
        return NULL;
    // 创建三个指针
    ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;
    while(n2){
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
            n3 = n3->next;
    }
    return n1;
}

链表的中间节点

题目链接：LeetCode - 链表的中间节点

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

注意循环条件要用短路求值 fast != NULL && fast->next != NULL，防止空指针解引用。

时间复杂度：O(N)

// 链表的中间节点
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){
    // 创建快慢指针
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

合并两个有序链表

题目链接：LeetCode - 合并两个有序链表

遍历两个链表，比较节点值，小的尾插到新链表中。为了避免频繁的判空操作，可以使用哨兵位（dummy node）简化代码逻辑。

时间复杂度：O(N)

// 合并两个有序链表（使用哨兵位优化）
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;

    // 创建哨兵位
    ListNode* newHead, *newTail;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* l1 = list1;
    ListNode* l2 = list2;
    while(l1 != NULL && l2 != NULL){
        if(l1->val < l2->val){
            newTail->next = l1;
            newTail = newTail->next;
            l1 = l1->next;
        } else {
            newTail->next = l2;
            newTail = newTail->next;
            l2 = l2->next;
        }
    }
    // 接上剩余节点
    if(l1) newTail->next = l1;
    if(l2) newTail->next = l2;

    ListNode* retHead = newHead->next;
    free(newHead);
    return retHead;
}

链表分割

题目链接：牛客网 - 链表分割

思路是创建两个链表（小链表、大链表），遍历原链表，小于 x 的尾插到小链表，大于等于 x 的尾插到大链表。最后将大小链表首尾相连。

同样建议使用哨兵位来减少边界判断。

// 链表分割
typedef struct ListNode ListNode;
class Partition{
public:
    ListNode* partition(ListNode* pHead, int x){
        // 创建两个带哨兵位的空链表
        ListNode* lessHead, *lessTail;
        lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* greatHead, *greatTail;
        greatHead = greatTail = (ListNode*)malloc(sizeof(ListNode));
        
        ListNode* pcur = pHead;
        while(pcur){
            if(pcur->val < x){
                lessTail->next = pcur;
                lessTail = lessTail->next;
            } else {
                greatTail->next = pcur;
                greatTail = greatTail->next;
            }
            pcur = pcur->next;
        }
        // 大链表尾节点的 next 指针置为 NULL(避免链表成环)
        greatTail->next = NULL;
        // 大小链表首尾相连
        lessTail->next = greatHead->next;
        
        ListNode* ret = lessHead->next;
        free(lessHead);
        free(greatHead);
        return ret;
    }
};

链表的回文结构

题目链接：牛客网 - 链表的回文结构

判断回文主要有两种思路：

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

推荐使用反转法，更高效。

/* struct ListNode { int val; struct ListNode *next; ... }; */
class PalindromeList{
public:
    // 找中间节点
    struct ListNode* middleNode(struct ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 反转链表
    struct ListNode* reverseList(struct ListNode* head){
        if(head == NULL) return NULL;
        ListNode* n1 = NULL, *n2 = head, *n3 = n2->next;
        while(n2){
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3) n3 = n3->next;
        }
        return n1;
    }

    bool chkPalindrome(ListNode* A){
        // 1. 找中间节点
        ListNode* mid = middleNode(A);
        // 2. 反转以中间节点为头的链表
        ListNode* right = reverseList(mid);
        // 3. 遍历原链表和反转后的链表，比较节点的值是否相等
        ListNode* left = A;
        while(right){
            if(left->val != right->val) return false;
            left = left->next;
            right = right->next;
        }
        return true;
    }
};

相交链表

题目链接：LeetCode - 相交链表

思路是求两个链表的长度，让长链表先走长度差步，然后长短链表同步遍历，找到第一个相同的节点。如果遍历结束都没相遇，则不相交。

时间复杂度：O(N)

// 相交链表
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB){
    // 求链表的长度
    ListNode* pa = headA;
    ListNode* pb = headB;
    int sizeA = 0, sizeB = 0;
    while(pa){ ++sizeA; pa = pa->next; }
    while(pb){ ++sizeB; pb = pb->next; }

    // 求长度差
    int gap = abs(sizeA - sizeB);

    // 定义长短链表
    ListNode* shortList = headA;
    ListNode* longList = headB;
    if(sizeA > sizeB){
        longList = headA;
        shortList = headB;
    }

    // 让长链表先走 gap
    while(gap--){
        longList = longList->next;
    }

    // 同一起跑线开始遍历
    while(shortList){
        if(shortList == longList) return shortList;
        shortList = shortList->next;
        longList = longList->next;
    }
    return NULL;
}

环形链表（快慢指针）

环形链表 I

题目链接：LeetCode - 环形链表 I

快慢指针，慢指针每次走一步，快指针每次走两步。如果链表有环，快指针最终一定会追上慢指针。

为什么能追上？ 假设进入环时两者距离为 N，每走一次距离缩小 1，所以必然相遇。即使快指针一次走 3 步、4 步，只要步长与慢指针互质，理论上也能相遇，但标准做法是 2 倍速最稳妥。

时间复杂度：O(N)

// 环形链表 I
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) return true;
    }
    return false;
}

环形链表 II

题目链接：LeetCode - 环形链表 II

在检测到环后，如何找到入环节点？

数学推导表明：相遇点到入环节点的距离 == 头结点到入环节点的距离。因此，当一个指针从头结点出发，另一个指针从相遇点出发，每次各走一步，它们再次相遇的点就是入环节点。

// 环形链表 II
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head){
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            // 相遇点---找入环节点
            ListNode* pcur = head;
            while(pcur != slow){
                pcur = pcur->next;
                slow = slow->next;
            }
            return pcur;
        }
    }
    return NULL;
}

原理简述：设头到入口距离 L，环长 R，入口到相遇点距离 X。快指针路程是慢指针两倍，即 2(L+X) = L+X+nR，化简得 L = nR-X。这意味着从头走 L 步和从相遇点走 L 步（绕环 n-1 圈后再走 R-X）会相遇。