数据结构：顺序表与链表核心算法实战 | 极客日志

C算法

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

顺序表与链表核心算法实战，涵盖双指针移除元素、有序数组去重与合并，以及链表反转、中间节点查找、回文判断和环检测等。通过快慢指针、三指针及哨兵位等技巧，深入解析时间复杂度 O(N)、空间复杂度 O(1) 的优化方案，适合数据结构初学者巩固基础。

imJackJia发布于 2026/3/27更新于 2026/4/252 浏览

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

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

移除元素

题目链接：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){
    // 创建两个变量，分别指向数组起始和下一个位置
     src = , dst = ;
    (src < numsSize){
        
        (nums[src] != nums[dst] && ++dst != src){
            nums[dst] = nums[src];
        }
        src++;
    }
     dst + ;
}

// 合并两个有序数组
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--];
    }
}

// 移除链表元素
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;
}

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

// 链表的中间节点
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;
}

// 合并两个有序链表（使用哨兵位优化）
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;
}

// 链表分割
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;
    }
};

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

// 相交链表
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
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
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;
}