算法题-day8-单链表C语言

2025-09-19 约 5207 字预计阅读 11 分钟

https://bing.ee123.net/img/rand?artid=151873075

算法题 day8—单链表(C语言)

题一 :

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    typedef struct ListNode ListNode;
    ListNode* removeElements(ListNode* head, int val) {
        //创建新链表
        ListNode* newHead,*newTail;
        newHead = newTail = NULL;

        ListNode* pcur = head;
        while(pcur)
        {
            //把值不为val的结点尾插到新链表中
            if(pcur->val!=val)
            {
                //尾插
                //链表为空
                if(newHead== NULL)
                {
                    newHead = newTail = pcur;
                }
                else{
                    //链表非空
                    newTail->next = pcur;
                    newTail = newTail->next;
                }
            }
            pcur = pcur->next;
        }
        //pcur为空
        if(newTail)
        {
           newTail->next = NULL;
        }
        return newHead;
    }
};

思路:

步骤1：初始化变量
定义 newHead  和 newTail  指针，分别指向新链表的头节点和尾节点，初始都为 NULL 。
定义 pcur  指针，从原链表的 head  开始遍历。
步骤2：遍历原链表
通过 while (pcur)  循环遍历原链表的每个节点：
判断节点值是否需要保留：若 pcur->val != val （节点值不等于目标值 val ），则将该节点加入新链表。
新链表为空的情况：若 newHead == NULL ，说明新链表还没有节点，此时让 newHead  和 newTail  都指向当前 pcur  节点。
新链表非空的情况：若 newHead != NULL ，则将当前 pcur  节点“尾插”到新链表中—— newTail->next = pcur ，然后更新 newTail  为当前 pcur  节点。
每次循环结束后， pcur  后移（ pcur = pcur->next ），继续遍历原链表的下一个节点。
步骤3：处理新链表的尾部
遍历结束后，若 newTail  不为 NULL ，将其 next  置为 NULL （防止新链表尾部残留指针形成环）。
步骤4：返回新链表的头节点
最终返回 newHead ，即删除所有 val  后的新链表头。
复杂度分析:
时间复杂度： O(n) ， n  是链表节点数，只需遍历一次原链表。
空间复杂度： O(1) ，仅用几个指针变量，无额外空间开销。

题二 :

思路 :

创建三个指针进行链表反转

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //链表为空
    if(head == NULL)
    {
        return head;
    }
    //创建三个指针
    ListNode* n1,*n2,*n3;
    n1 = NULL,n2 = head,n3 = n2->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        {
            n3 = n3->next;
        }
    }
    return n1;
}
步骤1：处理空链表情况
如果输入的链表头节点 head  为 NULL ，直接返回 head 。
步骤2：初始化三个指针
n1  初始为 NULL （表示当前节点的前一个节点）。
n2  初始为 head （表示当前要处理的节点）。
n3  初始为 n2->next （表示当前节点的后一个节点，用于保存后续节点的位置）。
步骤3：迭代反转链表指针
循环处理每个节点，直到 n2  为 NULL ：
将 n2  的 next  指针指向 n1 （实现当前节点的指针反转）。
依次将 n1  后移为 n2 ， n2  后移为 n3 。
如果 n3  不为 NULL ，将 n3  后移为 n3->next 。
步骤4：返回反转后的头节点
循环结束后， n1  指向的就是反转后链表的头节点，返回 n1 。
复杂度分析:
时间复杂度： O(n) ， n  是链表节点数，只需遍历一次链表。
空间复杂度： O(1) ，仅用三个指针变量，无额外空间开销。
这种方法的核心是“逐个反转指针方向”，通过迭代实现了高效的链表反转，是链表操作中的经典解法。

题三 :

思路 :

快慢指针

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode; 
struct ListNode* middleNode(struct ListNode* head) {
    //定义快慢指针
    ListNode* slow = head;
    ListNode* fast = head;

    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

    }
    return slow;
}

解题步骤

1. 初始化指针：定义慢指针 slow  和快指针 fast ，都从链表头节点 head  开始。
2. 遍历链表：循环条件为 fast != NULL && fast->next != NULL （保证快指针能合法后移）。
慢指针 slow  每次后移1步（ slow = slow->next ）。
快指针 fast  每次后移2步（ fast = fast->next->next ）。
3. 返回结果：当快指针遍历结束时，慢指针 slow  恰好指向链表的中间节点，返回 slow  即可。

复杂度分析:
时间复杂度： O(n) ， n  是链表节点数，快慢指针只需遍历一次链表。
空间复杂度： O(1) ，仅用两个指针变量，无额外空间开销。

这种方法的核心是“快慢指针的速度差”——快指针走2步，慢指针走1步，当快指针走到链表末尾时，慢指针自然停在中间位置，完美契合题目“找中间节点”的需求。

题四 :

思路:

这道题是合并两个有序链表，核心思路是双指针遍历 + 尾插法，通过比较两个链表节点的值，将较小的节点依次“尾插”到新链表中，最终得到一个有序的合并链表。

具体步骤（以“带头节点”的写法为例）

1. 边界处理：若其中一个链表为空，直接返回另一个链表。
2. 创建带头节点的新链表：预先分配一个空的头节点（仅用于占位），定义 newHead （头节点）和 newTail （尾节点）指向它。
3. 双指针遍历原链表：定义 l1  指向 list1  头节点， l2  指向 list2  头节点，循环比较 l1->val  和 l2->val ：
若 l1->val  更小，将 l1  尾插到新链表， l1  后移。
若 l2->val  更小（或相等），将 l2  尾插到新链表， l2  后移。
4. 处理剩余节点：若其中一个链表遍历完毕，将另一个链表的剩余节点直接挂到新链表尾部。
5. 释放头节点并返回结果：跳过头节点（返回 newHead->next ），并释放头节点的内存，避免泄漏。

这种方法的时间复杂度是 O(n + m) （ n 、 m 分别是两个链表的长度），空间复杂度是 O(1) （仅用几个指针，无额外空间开销），是合并有序链表的经典高效解法。

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
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 = NULL;

    ListNode* l1 = list1;
    ListNode* l2 = list2;

    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            //l1尾插到新链表中
            if(newHead == NULL)
            {
                newHead = newTail = l1;
            }
            else
            {
                //链表非空
                newTail->next = l1;
                newTail = newTail->next;
            }
            l1 = l1->next;
        }
        else
        {
            //l2尾插到新链表中
            if(newHead == NULL)
            {
                newHead = newTail = l2;
            }
            else
            {
                //链表非空
                newTail->next = l2;
                newTail = newTail->next;
            }
            l2 = l2->next;
        }
    }
    //要么l1为空 要么l2为空
    if(l2)
    {
        newTail->next = l2;
    }
    if(l1)
    {
        newTail->next = l1;
    }
    return newHead;
}

仔细观察上面的代码有很多重复的代码那么我们可以对上面的代码进行优化:

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 && l2)
    {
        if(l1->val < l2->val)
        {
            //l1尾插到新链表中
            newTail->next = l1;
            newTail = newTail->next;
            l1 = l1->next;
        }
        else
        {
            //l2尾插到新链表中
            newTail->next = l2;
            newTail = newTail->next;
            l2 = l2->next;
        }
    }
    //要么l1为空 要么l2为空
    if(l2)
    {
        newTail->next = l2;
    }
    if(l1)
    {
        newTail->next = l1;
    }

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

第一段代码（不带头节点）的“麻烦”主要体现在插入逻辑的分支判断上，而第二段代码（带头节点）通过“占位头节点”消除了这种分支，让逻辑更简洁。具体分析如下：

第一段代码的“麻烦点”:
在插入第一个节点时，需要判断 newHead == NULL ：
若为空（新链表第一个节点），需同时将 newHead  和 newTail  指向当前节点。
若不为空（后续节点），则通过 newTail->next  挂载节点，再更新 newTail 。
这种分支判断增加了代码的复杂度，且容易在逻辑中出现疏漏（比如忘记处理空链表的初始插入）。

第二段代码的优化逻辑:
通过预先创建一个空的头节点（仅用于占位，不存储有效数据），可以让所有插入操作“归一化”：
无论新链表是否为空，都可以通过 newTail->next  直接挂载节点，无需再判断 newHead == NULL 。
最终只需跳过头节点（返回 newHead->next ），并释放头节点的内存即可。
这种方式消除了插入逻辑的分支，让代码更简洁易维护，因此在实际开发中更推荐使用“带头节点”的写法来处理链表合并这类场景。

题五 :

思路一:


    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;
        int right = i-1;
        while(left<right)
        {
            if(arr[left]!=arr[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

这段代码的步骤如下：
1. 初始化数组：定义一个大小为900的数组 arr ，用于存储链表节点的值。
2. 遍历链表存值：定义指针 pcur 指向链表头 A ，循环遍历链表，将每个节点的 val 依次存入数组 arr ，同时记录元素个数 i 。
3. 双指针验证回文：定义左指针 left 从数组起始位置开始，右指针 right 从数组末尾位置开始，循环比对 arr[left] 和 arr[right] 的值。若存在不相等的情况，返回 false ；若全部比对相等，返回 true 。

思路二:

//找中间节点
ListNode* middleNode(ListNode* head) {
    ListNode* slow, *fast;
    slow = fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

//反转链表
ListNode* reverseList(ListNode* head) {
    //链表为空
    if (head == NULL) {
        return head;
    }
    //创建三个指针
    ListNode* n1, *n2, *n3;
    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) {
    //找中间节点
    ListNode* mid = middleNode(A);
    //反转中间节点之后的链表
    ListNode* right = reverseList(mid);
    //遍历原链表和反转后的链表
    ListNode* left = A;
    while (right) {
        if (left->val != right->val) {
            return false;
        }
        left = left->next;
        right = right->next;
    }
    return true;
}

这段代码判断链表是否为回文结构的步骤如下：

1. 找中间节点：
定义快慢指针 slow  和 fast ，初始都指向链表头 head 。
循环条件： fast  不为空且 fast->next  不为空。
慢指针 slow  每次走1步，快指针 fast  每次走2步。
循环结束后， slow  指向链表的中间节点，返回 slow 。
2. 反转链表：
若链表为空，直接返回 head 。
定义三个指针 n1 （前一个节点，初始为 NULL ）、 n2 （当前节点，初始为 head ）、 n3 （后一个节点，初始为 n2->next ）。
循环条件： n2  不为空。
将 n2->next  指向 n1 （反转当前节点指针），然后 n1  后移为 n2 ， n2  后移为 n3 ，若 n3  不为空， n3  后移为 n3->next 。
循环结束后， n1  指向反转后链表的头节点，返回 n1 。
3. 判断回文结构：
调用 middleNode  函数找到链表中间节点 mid 。
调用 reverseList  函数反转 mid  之后的链表，得到 right 。
定义 left  指向原链表头 A ，同时遍历 left  和 right 。
若存在 left->val != right->val  的情况，返回 false ；若遍历结束所有值都相等，返回 true 。

这段代码复用了前面几个算法题的核心逻辑，属于“算法模块复用”的典型场景：

找中间节点：复用了「876. 链表的中间结点」的快慢指针法。
反转链表：复用了「206. 反转链表」的三指针迭代法。

通过将这两个独立的算法模块组合起来，最终实现了“判断链表回文结构”的功能，体现了算法题中“模块化思维”的重要性——把复杂问题拆解为多个已解决的子问题，再整合求解。

题六 :

思路 :

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
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);//abs函数：用于求绝对值
    //让长链表先走gap步
    ListNode* shortList = headA;
    ListNode* longList = headB;
    if(sizeA > sizeB)
    {
        longList = headA;
        shortList = headB;
    }
    while(gap--)
    {
        longList = longList->next;
    }
    //longList shortList在同一起跑线
    while(shortList)
    {
        if(longList == shortList)
        {
            return longList;
        }
        shortList = shortList->next;
        longList = longList->next;
    }
    return NULL;
}

核心思路是让两个链表在“同一起跑线”上遍历，从而找到相交节点：
步骤1：统计两个链表的长度
分别遍历链表 headA  和 headB ，记录它们的节点个数，记为 sizeA  和 sizeB 。
步骤2：计算长度差并让长链表“补步”
计算两个链表的长度差 gap （取绝对值）。
区分“长链表”和“短链表”：若 sizeA  更大，那么 headA  是长链表， headB  是短链表；反之则交换。
让长链表的指针从表头开始，先走 gap  步，使两个链表剩余的未遍历长度相同。
步骤3：同步遍历找相交节点
同时从短链表的表头和长链表“补步”后的位置开始遍历：
若两个指针指向同一个节点，说明该节点是相交的起始节点，返回此节点。
若遍历完整个短链表，两个指针仍未指向同一节点，说明两链表不相交，返回 null 。
复杂度:
时间复杂度： O(n + m) （ n 、 m 分别为两个链表长度，遍历两次链表）。
空间复杂度： O(1) （仅用几个指针，无额外空间开销）。

题七 : 1

思路:

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

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

1. 初始化指针：定义慢指针 slow  和快指针 fast ，都从链表头节点 head  开始。
2. 遍历链表：循环条件为 fast != NULL && fast->next != NULL （保证快指针能合法后移）。
慢指针 slow  每次后移1步。
快指针 fast  每次后移2步。
3. 判断是否有环：若在遍历过程中 slow  和 fast  相遇（ slow == fast ），说明链表有环，返回 true ；若快指针遍历到链表末尾（循环结束），说明链表无环，返回 false 。
时间复杂度： O(n) 。若链表有环，快慢指针最多遍历一圈就会相遇；若链表无环，快指针遍历到末尾即可，因此时间复杂度是线性的。
空间复杂度： O(1) 。仅用两个指针变量，无额外空间开销。

该方法的核心是利用“快慢指针的速度差”——若链表有环，快指针最终会在环内追上慢指针；若链表无环，快指针会先到达链表末尾，从而高效判断链表是否有环。

题八 :

思路:

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
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;
            //pcur slow
            while(pcur != slow)
            {
                pcur = pcur->next;
                slow = slow->next;
            }
            //pcur == slow
            return pcur;
        }
    }
    return NULL;
}

核心是利用“快慢指针相遇后，头节点到入环起点的距离等于相遇点到入环起点的距离”这一规律：
步骤1：找快慢指针的相遇点
初始化慢指针 slow  和快指针 fast ，都指向链表头 head 。
循环条件： fast  不为空且 fast->next  不为空（保证快指针能合法移动）。
慢指针 slow  每次走 1步。
快指针 fast  每次走 2步。
若 slow == fast ，说明链表有环，记录此时的相遇点；若循环结束快指针到了链表末尾，说明无环，返回 NULL 。
步骤2：找入环的起始节点
定义新指针 pcur ，指向链表头 head 。
同时遍历 pcur （从头节点出发）和 slow （从相遇点出发），每次都走1步。
当 pcur == slow  时，此时的节点就是入环的起始节点，返回该节点。
原理补充
假设头节点到入环起点的距离为 a ，入环起点到相遇点的距离为 b ，环的长度为 c 。
慢指针走的路程： a + b 。
快指针走的路程： a + b + n×c （ n  是快指针在环内绕的圈数）。
由于快指针速度是慢指针的2倍，所以 2(a + b) = a + b + n×c ，化简得 a = n×c - b 。这意味着“头节点到入环起点的距离”等于“相遇点到入环起点的距离（绕环 n-1  圈后剩余的距离）”，因此让 pcur  和 slow  同步走，最终会在入环起点相遇。
通过这两步，就能高效找到环形链表的入环起始节点，时间复杂度为 O(n) ，空间复杂度为 O(1)

总结:

这篇文章摘要总结了8个链表相关算法题的解题思路和代码实现：

移除元素 - 通过创建新链表，遍历原链表将非目标值节点尾插到新链表
反转链表 - 使用三指针迭代法逐个反转节点指针方向
链表中点 - 快慢指针法，快指针走2步慢指针走1步
合并有序链表 - 双指针遍历+尾插法，比较节点值大小依次插入
回文链表 - 两种方法：转数组验证或快慢指针+反转后半部分
相交链表 - 计算长度差后同步遍历找交点
环形链表1 - 快慢指针判断是否有环
环形链表2 - 快慢指针找入环点，利用数学规律定位

各题均采用高效解法，时间复杂度主要为O(n)，空间复杂度主要为O(1)。文章展示了链表操作的经典技巧，如快慢指针、双指针、反转等，并强调模块化思维的重要性。

目录

算法题-day8-单链表C语言

算法题 day8—单链表(C语言)

题一 :

代码:

思路:

题二 :

思路 :

代码:

题三 :

思路 :

代码:

题四 :

思路:

代码:

题五 :

思路一:

思路二:

题六 :

思路 :

代码:

题七 : 1

思路:

代码:

题八 :

思路:

代码:

总结: