顺序表与链表核心算法实战：双指针与快慢指针详解

合并两个有序数组

思路解析：为了避免覆盖 nums1 中尚未处理的元素，建议从后往前遍历。定义三个指针分别指向 nums1 末尾有效数据、nums2 末尾以及合并后的末尾位置。比较大小，将较大者填入末尾。

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

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

移除链表元素

思路解析：可以通过尾插法构建新链表，或者原地修改指针。这里演示通过遍历原链表，将非目标值的节点依次连接到新链表中。注意最后要将新链表的尾节点 next 置为 NULL，防止成环。

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

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

反转链表

思路解析：提供两种主流解法。

1. 头插法：遍历原链表，将每个节点插入到新链表的头部。需注意保存下一个节点，并将原头节点的 next 置空。
2. 三指针法：维护 prev, curr, next 三个指针，逐个改变指向。此方法更直观且不易出错。

// 方法一：头插法
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;
}

// 方法二：三指针法
struct ListNode* reverseList_v2(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;
}

链表的中间节点

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

• 时间复杂度：O(N)

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

合并两个有序链表

思路解析：创建哨兵位（Dummy Node）可以简化边界处理。比较两个链表当前节点的值，将较小的节点尾插到新链表中。遍历结束后，将剩余的非空部分直接接上。

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

    // 创建哨兵位
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    ListNode* tail = dummy;
    ListNode* l1 = list1;
    ListNode* l2 = list2;

    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    // 连接剩余部分
    if (l1) tail->next = l1;
    if (l2) tail->next = l2;

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

链表分割

思路解析：维护两个子链表（小于 x 和大于等于 x），遍历原链表进行尾插。最后将两个链表首尾相连。注意大链表尾部必须置空，防止成环。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* lessHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* lessTail = lessHead;
        ListNode* greatHead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* greatTail = greatHead;
        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;
        }
        greatTail->next = NULL;
        lessTail->next = greatHead->next;
        
        ListNode* ret = lessHead->next;
        free(lessHead);
        free(greatHead);
        return ret;
    }
};

链表的回文结构

思路解析：

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

bool chkPalindrome(ListNode* A) {
    int arr[900] = {0};
    ListNode* pcur = A;
    int i = 0;
    while (pcur) {
        arr[i++] = pcur->val;
        pcur = pcur->next;
    }
    int left = 0, right = i - 1;
    while (left < right) {
        if (arr[left] != arr[right]) return false;
        left++; right--;
    }
    return true;
}

相交链表

思路解析：计算两链表长度，长链表先走差值步，使两指针处于同一起跑线，同步遍历直到相遇。若不相交则返回 NULL。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    ListNode* pa = headA, *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, *longList = headB;
    if (sizeA > sizeB) {
        longList = headA; shortList = headB;
    }

    while (gap--) longList = longList->next;

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

环形链表（快慢指针）

环形链表 I

思路解析：快指针每次走两步，慢指针每次走一步。若存在环，快指针终将追上慢指针。证明表明只要速度差为 1，在有限环内必然相遇。

bool hasCycle(struct ListNode* head) {
    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) {
    ListNode* slow = head, *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;
}

以上算法涵盖了顺序表与链表中最核心的操作模式。在实际开发中，理解指针的移动规律和边界条件的处理比单纯记忆代码更重要。希望这些示例能帮助你更好地掌握数据结构底层逻辑。