风落青芜头像
顺序表与链表经典算法题详解(C语言)封面图

顺序表与链表经典算法题详解(C语言)

前言

在学习数据结构的过程中,顺序表和链表是非常重要的基础内容。本篇主要整理顺序表和单链表中比较经典的算法题。

1. 移除元素

题目链接: LeetCode 27. 移除元素

解题思路

这道题可以使用双指针法解决。

定义两个下标:

  • src:遍历原数组,寻找需要保留的元素。
  • dst:指向新数组中下一个存放元素的位置。

遍历数组,如果当前元素不等于 val,就将其放到 dst 位置,然后 dst++;如果相等,则直接跳过。

遍历结束后,dst 就是删除元素后的数组长度。

例如:

原数组:[3, 2, 2, 3, 4]
val = 3

处理后:[2, 2, 4]
返回:3

代码实现

int removeElement(int* nums, int numsSize, int val)
{
    int dst = 0;

    for (int src = 0; src < numsSize; src++)
    {
        if (nums[src] != val)
        {
            nums[dst] = nums[src]; // 保留当前元素
            dst++;                 // 目标位置后移
        }
    }

    return dst;
}

复杂度分析

  • 时间复杂度:O(N),遍历一次数组。
  • 空间复杂度:O(1),原地修改数组。

2. 删除有序数组中的重复项

题目链接: LeetCode 26. 删除有序数组中的重复项

解题思路

由于数组已经按照升序排列,相同的元素一定连续出现,因此可以使用双指针法。

定义两个指针:

  • slow:指向已经保留的最后一个不重复元素。
  • fast:负责向后遍历数组,寻找新的不重复元素。

首先让 slow 指向第一个元素,fast 从第二个元素开始遍历。

如果 nums[fast] 与 nums[slow] 不相等,说明找到了新的元素,将 slow 后移一位,并把新元素放到对应位置。

如果相等,则说明出现了重复元素,直接跳过。

最后返回 slow + 1,即不重复元素的个数。

代码实现

int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize == 0)
        return 0;

    int slow = 0;

    for (int fast = 1; fast < numsSize; fast++)
    {
        if (nums[fast] != nums[slow])
        {
            slow++;
            nums[slow] = nums[fast]; // 保存新的不重复元素
        }
    }

    return slow + 1;
}

复杂度分析

  • 时间复杂度:O(N),只遍历一次数组。
  • 空间复杂度:O(1),不需要额外空间。

3. 合并两个有序数组

题目链接: LeetCode 88. 合并两个有序数组

解题思路

这道题可以使用三个指针,从后往前进行合并。

定义三个下标:

  • i:指向 nums1 最后一个有效元素。
  • j:指向 nums2 最后一个元素。
  • k:指向 nums1 最后一个位置。

每次比较 nums1[i] 和 nums2[j],将较大的元素放到 nums1[k],然后移动对应指针。

为什么要从后往前合并?

因为 nums1 后面已经预留了空间,如果从前往后合并,可能会覆盖原来还没有处理的元素。从后往前则不会出现这个问题。

当 nums2 中的元素全部放入后,合并结束。因为 nums1 剩余的元素本来就在正确的位置。

代码实现

void merge(int* nums1, int m, int* nums2, int n)
{
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;

    while (j >= 0)
    {
        if (i >= 0 && nums1[i] > nums2[j])
        {
            nums1[k--] = nums1[i--]; // 放入较大的元素
        }
        else
        {
            nums1[k--] = nums2[j--];
        }
    }
}

复杂度分析

  • 时间复杂度:O(M+N),两个数组中的元素最多遍历一次。
  • 空间复杂度:O(1),直接在原数组中完成合并。

4. 移除链表元素

题目链接: LeetCode 203. 移除链表元素

解题思路

遍历链表,删除所有值等于 val 的结点。

这里使用虚拟头结点(哨兵结点),可以统一处理头结点和普通结点的删除操作。

创建一个虚拟头结点 dummy,让它指向原链表头结点,再使用 cur 指针遍历链表。

  • 如果 cur->next 的值等于 val,就删除该结点。
  • 否则让 cur 向后移动。

需要注意:删除结点后,cur 不需要移动,因为新的 cur->next 仍然需要判断,避免漏掉连续出现的目标元素。

代码实现

struct ListNode* removeElements(
    struct ListNode* head, int val)
{
    struct ListNode dummy;
    dummy.next = head; // 虚拟头结点指向原链表

    struct ListNode* cur = &dummy;

    while (cur->next != NULL)
    {
        if (cur->next->val == val)
        {
            struct ListNode* del = cur->next;

            cur->next = del->next; // 跳过需要删除的结点
            free(del);             // 释放结点空间
        }
        else
        {
            cur = cur->next; // 不需要删除,继续遍历
        }
    }

    return dummy.next; // 返回新的头结点
}

复杂度分析

  • 时间复杂度:O(N),遍历一次链表。
  • 空间复杂度:O(1),只使用常数个额外变量。

5. 反转链表

题目链接: LeetCode 206. 反转链表

解题思路

反转链表就是改变每个结点 next 指针的指向,使其指向前一个结点。

例如:

原链表:1 -> 2 -> 3 -> NULL

反转后:3 -> 2 -> 1 -> NULL

这里使用三个指针:

  • prev:记录当前结点的前一个结点。
  • cur:当前正在处理的结点。
  • next:提前保存当前结点的下一个结点。

每次先保存 next,再修改 cur->next,然后依次移动三个指针。

为什么需要 next?

因为修改 cur->next 后,原来的后续结点就可能丢失,所以必须提前保存。

遍历结束后,prev 就是反转后的新头结点。

代码实现

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;

    while (cur != NULL)
    {
        struct ListNode* next = cur->next; // 保存下一个结点

        cur->next = prev; // 反转当前结点的指针

        prev = cur;       // prev 向后移动
        cur = next;       // cur 继续处理下一个结点
    }

    return prev; // 返回反转后的新头结点
}

复杂度分析

  • 时间复杂度:O(N),每个结点只处理一次。
  • 空间复杂度:O(1),只使用三个指针。

6. 链表的中间结点

题目链接: LeetCode 876. 链表的中间结点

解题思路

这道题可以使用快慢指针法。

定义两个指针:

  • slow:慢指针,每次移动一步。
  • fast:快指针,每次移动两步。

两个指针都从链表头结点开始。当快指针到达链表末尾时,慢指针刚好位于链表中间。

例如:

1 -> 2 -> 3 -> 4 -> 5 -> 6
          ↑
        中间位置

由于快指针一次走两步,慢指针一次走一步,因此当快指针走完整个链表时,慢指针只走了一半。

另外,如果链表长度为偶数,慢指针最终会指向第二个中间结点,符合题目要求。

代码实现

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    // 快指针必须保证能够向后移动两步
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;           // 慢指针走一步
        fast = fast->next->next;     // 快指针走两步
    }

    return slow;
}

复杂度分析

  • 时间复杂度:O(N),快指针最多遍历链表的一半。
  • 空间复杂度:O(1),只使用两个指针。

7. 合并两个有序链表

题目链接: LeetCode 21. 合并两个有序链表

解题思路

两个链表都已经按照升序排列,因此只需要比较当前结点的值,将较小的结点连接到新链表的末尾。

这里使用虚拟头结点 dummy 和尾指针 tail。

具体步骤:

  1. 创建虚拟头结点,让 tail 指向它。
  2. 比较两个链表当前结点的值。
  3. 将较小的结点连接到 tail 后面。
  4. 移动对应链表的指针,同时移动 tail。
  5. 当其中一个链表遍历结束后,将另一个链表剩余部分直接连接。

这里不需要重新创建数据结点,直接调整原链表结点的指针即可。

代码实现

struct ListNode* mergeTwoLists(
    struct ListNode* list1,
    struct ListNode* list2)
{
    struct ListNode dummy;
    dummy.next = NULL;

    struct ListNode* tail = &dummy;

    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val <= list2->val)
        {
            tail->next = list1; // 连接较小的结点
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            list2 = list2->next;
        }

        tail = tail->next; // 尾指针向后移动
    }

    // 将剩余链表直接连接到尾部
    tail->next = (list1 != NULL) ? list1 : list2;

    return dummy.next;
}

复杂度分析

  • 时间复杂度:O(M+N),每个结点最多访问一次。
  • 空间复杂度:O(1),不需要额外创建数据结点。

8. 链表分割

题目链接: 牛客网:链表分割

解题思路

这道题要求将链表分成两个部分:

  • 第一部分存放所有小于 x 的结点。
  • 第二部分存放所有大于或等于 x 的结点。

同时还需要保证每一部分内部原来的相对顺序不变。

可以使用两个链表分别存放这两类结点,再将它们连接起来。

具体做法:

  1. 创建两个虚拟头结点,分别表示两条链表。
  2. 使用两个尾指针,负责将结点插入对应链表的末尾。
  3. 遍历原链表,根据结点值决定插入哪条链表。
  4. 最后将两条链表连接起来。

这里使用尾插法,可以保留结点原来的相对顺序。

代码实现

struct ListNode* partition(
    struct ListNode* pHead, int x)
{
    struct ListNode lessDummy;
    struct ListNode greaterDummy;

    lessDummy.next = NULL;
    greaterDummy.next = NULL;

    struct ListNode* lessTail = &lessDummy;
    struct ListNode* greaterTail = &greaterDummy;

    struct ListNode* cur = pHead;

    while (cur != NULL)
    {
        struct ListNode* next = cur->next; // 保存下一个结点
        cur->next = NULL;                  // 断开当前结点

        if (cur->val < x)
        {
            lessTail->next = cur; // 尾插到小于x的链表
            lessTail = cur;
        }
        else
        {
            greaterTail->next = cur; // 尾插到另一条链表
            greaterTail = cur;
        }

        cur = next;
    }

    // 将两条链表连接起来
    lessTail->next = greaterDummy.next;

    return lessDummy.next;
}

复杂度分析

  • 时间复杂度:O(N),只遍历一次原链表。
  • 空间复杂度:O(1),只使用常数个额外指针。

9. 链表的回文结构

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

解题思路

回文结构要求链表从前往后和从后往前读取的结果相同。

例如:

1 -> 2 -> 3 -> 2 -> 1

可以结合快慢指针和链表反转来解决。

具体步骤:

  1. 使用快慢指针找到链表的中间位置。
  2. 如果链表长度为奇数,跳过中间结点。
  3. 将后半部分链表反转。
  4. 分别遍历前半部分和反转后的后半部分,比较结点值。
  5. 如果所有对应结点都相同,则说明是回文结构。

例如:

原链表:1 -> 2 -> 3 -> 2 -> 1

反转后半部分:

前半部分:1 -> 2
后半部分:1 -> 2

两部分对应结点的值相同,因此是回文结构。

比较完成后,还可以再次反转后半部分,将原链表恢复。

代码实现

// 反转链表
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;

    while (cur != NULL)
    {
        struct ListNode* next = cur->next;

        cur->next = prev;

        prev = cur;
        cur = next;
    }

    return prev;
}

bool chkPalindrome(struct ListNode* A)
{
    if (A == NULL || A->next == NULL)
        return true;

    struct ListNode* slow = A;
    struct ListNode* fast = A;

    // 第一步:寻找链表中间位置
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 奇数个结点,跳过中间结点
    if (fast != NULL)
        slow = slow->next;

    // 第二步:反转后半部分
    struct ListNode* second = reverseList(slow);

    struct ListNode* p1 = A;
    struct ListNode* p2 = second;

    bool ret = true;

    // 第三步:比较前后两部分
    while (p2 != NULL)
    {
        if (p1->val != p2->val)
        {
            ret = false;
            break;
        }

        p1 = p1->next;
        p2 = p2->next;
    }

    // 第四步:恢复原链表
    reverseList(second);

    return ret;
}

复杂度分析

  • 时间复杂度:O(N),寻找中间结点、反转和比较都需要线性时间。
  • 空间复杂度:O(1),不需要额外数组或栈。

10. 相交链表

题目链接: LeetCode 160. 相交链表

解题思路

两个链表相交,指的是它们从某个结点开始共享后面的结点,而不是两个结点的数值相同。

这道题可以使用双指针法。

定义两个指针:

  • pA:从链表 A 的头结点开始。
  • pB:从链表 B 的头结点开始。

两个指针同时向后移动。当一个指针遍历完自己的链表后,就转到另一个链表的头部继续遍历。

为什么这样可以找到相交结点?

假设链表 A 的长度为 a,链表 B 的长度为 b,相交部分长度为 c。

那么两个指针最终走过的距离都是:

a + b - c

因此,如果两个链表相交,两个指针最终会在相交结点相遇;如果不相交,则最终都会到达 NULL。

代码实现

struct ListNode* getIntersectionNode(
    struct ListNode* headA,
    struct ListNode* headB)
{
    struct ListNode* pA = headA;
    struct ListNode* pB = headB;

    while (pA != pB)
    {
        // A链表遍历结束后,转到B链表
        pA = (pA == NULL) ? headB : pA->next;

        // B链表遍历结束后,转到A链表
        pB = (pB == NULL) ? headA : pB->next;
    }

    return pA; // 相交返回交点,不相交返回NULL
}

复杂度分析

  • 时间复杂度:O(M+N),最多遍历两个链表各一次。
  • 空间复杂度:O(1),只使用两个指针。

11. 环形链表 I

题目链接: LeetCode 141. 环形链表

解题思路

这道题需要判断链表中是否存在环,可以使用快慢指针法。

定义两个指针:

  • slow:每次走一步。
  • fast:每次走两步。

两个指针从链表头结点同时出发。

如果链表不存在环,快指针最终会走到 NULL。

如果链表存在环,快指针进入环后会不断追赶慢指针。

由于快指针每次比慢指针多走一步,因此两个指针之间的距离会不断缩小,最终一定会相遇。

所以,只需要判断两个指针是否相遇即可。

代码实现

bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;           // 慢指针走一步
        fast = fast->next->next;     // 快指针走两步

        if (slow == fast)
            return true;             // 相遇说明存在环
    }

    return false; // 快指针到达链表末尾,不存在环
}

复杂度分析

  • 时间复杂度:O(N),快慢指针最多遍历线性数量的结点。
  • 空间复杂度:O(1),只使用两个指针。

12. 环形链表 II

题目链接: LeetCode 142. 环形链表 II

解题思路

这道题是在环形链表 I 的基础上,进一步寻找环的入口。

同样使用快慢指针,分为两个阶段。

第一阶段:寻找相遇点。

慢指针每次走一步,快指针每次走两步。如果两者相遇,说明链表存在环。

第二阶段:寻找环的入口。

快慢指针相遇后:

  1. 将一个新指针 p 放到链表头结点。
  2. 保留慢指针在相遇点。
  3. 两个指针每次都走一步。
  4. 两个指针再次相遇的位置就是环的入口。

原理推导:

假设:

  • L:链表头结点到环入口的距离。
  • X:环入口到第一次相遇点的距离。
  • C:环的周长。

快慢指针第一次相遇时,慢指针走过的距离为:

L + X

快指针走过的距离为:

L + X + nC

其中 n 表示快指针比慢指针多绕过的环的圈数。

由于快指针的速度是慢指针的两倍:

2(L + X) = L + X + nC

整理得到:

L + X = nC

L = nC - X

这说明,从链表头结点出发走 L 步,与从相遇点出发走 L 步,最终都会到达环的入口。

因此,让两个指针分别从头结点和相遇点出发,每次走一步,最终就会在环入口相遇。

代码实现

struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    // 第一阶段:寻找快慢指针的相遇点
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast)
        {
            // 第二阶段:寻找环的入口
            struct ListNode* p = head;

            while (p != slow)
            {
                p = p->next;       // 从头结点出发
                slow = slow->next; // 从相遇点出发
            }

            return p; // 返回环的入口
        }
    }

    return NULL; // 不存在环
}

复杂度分析

  • 时间复杂度:O(N),寻找相遇点和环入口都只需要线性时间。
  • 空间复杂度:O(1),只使用常数个指针。

13. 随机链表的复制

题目链接: LeetCode 138. 随机链表的复制

解题思路

这道题的链表结点除了 next 指针,还有一个 random 指针,可以指向任意结点或者 NULL。

要求复制整个链表,新链表中的结点必须是独立创建的,不能直接使用原链表的结点。

这里使用一种比较巧妙的方法:将复制结点插入原结点后面。

整个过程分为三个步骤。

第一步:复制结点。

遍历原链表,为每个结点创建一个新结点,并将它插入原结点后面。

例如:

原链表:A -> B -> C

插入后:A -> A' -> B -> B' -> C -> C'

这样,每个原结点的下一个结点就是它对应的复制结点。

第二步:复制 random 指针。

假设原结点 A 的 random 指向 C,那么复制结点 A’ 的 random 就应该指向 C’。

由于 C’ 就在 C 的后面,因此可以直接使用:

A->next->random = A->random->next;

这样就能找到对应的复制结点。

第三步:拆分链表。

将原链表和复制链表分离,恢复两个独立的链表。

最终得到:

原链表:A -> B -> C

复制链表:A' -> B' -> C'

代码实现

struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
        return NULL;

    struct Node* cur = head;

    // 第一步:复制结点,插入原结点后面
    while (cur != NULL)
    {
        struct Node* copy =
            (struct Node*)malloc(sizeof(struct Node));

        copy->val = cur->val;
        copy->random = NULL;

        copy->next = cur->next;
        cur->next = copy;

        cur = copy->next;
    }

    // 第二步:复制random指针
    cur = head;

    while (cur != NULL)
    {
        struct Node* copy = cur->next;

        if (cur->random != NULL)
        {
            // 原结点random指向的结点,其next就是对应的复制结点
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }

    // 第三步:拆分原链表和复制链表
    cur = head;

    struct Node* copyHead = head->next;

    while (cur != NULL)
    {
        struct Node* copy = cur->next;

        cur->next = copy->next; // 恢复原链表

        if (copy->next != NULL)
        {
            copy->next = copy->next->next; // 连接下一个复制结点
        }

        cur = cur->next;
    }

    return copyHead;
}

复杂度分析

  • 时间复杂度:O(N),需要遍历链表三次。
  • 空间复杂度:O(1),不计算新复制的结点所占空间。

算法思想总结

通过以上题目的学习,可以发现,很多算法题虽然题目不同,但使用的核心思想往往是相通的。以下是本篇涉及的几种常见算法思想。

  1. 双指针法
    双指针法通过设置两个指针,按照不同的规则移动,减少不必要的遍历,提高算法效率。

典型题目:

  • 移除元素
  • 删除有序数组中的重复项
  • 合并两个有序数组
  • 相交链表
  1. 快慢指针法
    快慢指针通常用于链表问题,通过控制两个指针不同的移动速度来解决问题。

典型题目:

  • 链表的中间结点
  • 链表的回文结构
  • 环形链表 I
  • 环形链表 II
  1. 虚拟头结点
    虚拟头结点是链表操作中非常实用的技巧。通过创建一个不存储有效数据的头结点,可以统一处理头结点和普通结点的插入、删除等操作,减少特殊情况的判断。

典型题目:

  • 移除链表元素
  • 合并两个有序链表
  • 链表分割
  1. 链表反转
    链表反转的核心是修改结点之间的指针指向,通常使用三个指针完成操作。掌握这一方法,也有助于解决一些需要反向比较或重新组织链表的问题。

典型题目:

  • 反转链表
  • 链表的回文结构

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/2601_96015117/article/details/170605137

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--