• 【LeetCode】链表OJ题

    ​🌠 作者：@阿亮joy.
    🎆专栏：《阿亮爱刷题》
    🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
    在这里插入图片描述

    活动地址：CSDN21天学习挑战赛

    目录



    👉合并两个有序链表👈

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    示例 1：
    输入：l1 = [1,2,4], l2 = [1,3,4]
    输出：[1,1,2,3,4,4]

    在这里插入图片描述

    示例 2：
    输入：l1 = [], l2 = []
    输出：[]

    示例 3：
    输入：l1 = [], l2 = [0]
    输出：[0]

    提示：

    • 两个链表的节点数目范围是 [0, 50]
    • -100 <= Node.val <= 100
    • l1 和 l2 均按非递减顺序排列

    思路：先定义两个指针head和tail，head为头指针，tail负责将链表l1、l2中较小的节点链接到链表的尾部。当l1或l2为空链表时，返回另一个链表。当l1和l2均不为空链表时，利用while循环，将l1、l2中较小的节点链接到tail上。当循环结束，l1或l2的节点还没链接到tail上，需要将其链接上。

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    //如果其中一个链表为空，就返回另一个链表
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    if(list1->val < list2->val)
    {
        //先让头指针不为NULL，下面就不需要重复判断了
        head = tail = list1;
        list1 = list1->next;
    }
    else
    {
        head = tail = list2;
        list2 = list2->next;
    }
    while(list1 && list2)
    {
        //谁小就链接到tail的后面
        if(list1->val < list2->val)
        {

            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    //将还有节点的链表链接到tail的后面
    if(list1)
    {
        tail->next = list1;
    }
    if(list2)
    {
        tail->next = list2;
    }
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    //如果其中一个链表为空，就返回另一个链表
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    //哨兵位的头结点，不存储有效数据
    head = tail = (struct ListNode*)(malloc(sizeof(struct ListNode)));
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {

            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    if(list1)
    {
        tail->next = list1;
    }
    if(list2)
    {
        tail->next = list2;
    }
    struct ListNode* list = head->next;
    free(head);
    return list;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    在这里插入图片描述

    👉分割链表👈

    给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

    你不需要保留每个分区中各节点的初始相对位置。

    示例 1：

    输入：head = [1,4,3,2,5,2], x = 3
    输出：[1,2,2,4,3,5]

    在这里插入图片描述

    示例 2：

    输入：head = [2,1], x = 2
    输出：[1,2]

    提示：

    • 链表中节点的数目在范围 [0, 200] 内
    • -100 <= Node.val <= 100
    • -200 <= x <= 200

    思路：
    在这里插入图片描述

    /*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x)
{

    struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;
    //开一个哨兵位的头结点，方便尾插
    lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    //将lessTail->next和greaterTail->next置为NULL，刚好对应链表为NULL的情况
    lessTail->next = NULL;
    greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    greaterTail->next = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val < x)
        {
            lessTail->next = cur;
            lessTail = cur;
        }
        else
        {
            greaterTail->next = cur;
            greaterTail =cur;
        }
        cur = cur->next;
    }
    lessTail->next = greaterHead->next;//将greater链表链接到less链表的尾部
    greaterTail->next = NULL;//防止链表成环
    //用newHead保存返回结果
    struct ListNode* newHead = lessHead->next;
    //释放动态申请的空间
    free(lessHead);
    free(greaterHead);
    return newHead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    👉回文链表👈

    给定一个链表的 头节点 head ，请判断其是否为回文链表。

    如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

    示例 1：

    在这里插入图片描述
    输入: head = [1,2,3,3,2,1]
    输出: true

    示例 2：
    在这里插入图片描述
    输入: head = [1,2]
    输出: false

    提示：

    • 链表 L 的长度范围为 [1, 10^5]
    • 0 <= node.val <= 9

    思路：先求出链表的中间节点，然后将中间节点后面的部分链表反转过来并定义一个反转链表的头节点rHead。因为中间节点的前一个节点还链接着中间节点，所以可以定义cur1 = head； cur2 = rHead。然后利用while循环依次比较cur1和cur2中的节点的值，如果值不相同，说明原链表不是回文链表，直接返回false。如果值相同，则需要比较下一个节点的值。当while循环结束，如果比较结果都是相同的话，说明原链表是回文链表，返回true。
    在这里插入图片描述

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//反转链表
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newHead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        //记录下一个节点
        struct ListNode* next = cur->next;
        //头插
        cur->next = newHead;
        newHead = cur;
        //迭代往后走
        cur = next;
    }
    return newHead;
}
//求链表的中间节点
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;//slow走一步
        fast = fast->next->next;//fast走两步
    }
    return slow;
}

bool isPalindrome(struct ListNode* head)
{
    struct ListNode* mid = middleNode(head);
    struct ListNode* rHead = reverseList(mid);

    struct ListNode* cur1 = rHead;
    struct ListNode* cur2 = head;
    while(cur1 && cur2)
    {
        if(cur1->val != cur2->val)
            return false;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    在这里插入图片描述

    注意：为了代码的美观，博主将求链表的中间节点和反转链表封装成了一个函数，其实这两个点也是单独的两道题目来的。如果不知道怎么来的话，可以看上一篇博客：链表OJ题。

    👉相交链表👈

    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

    图示两个链表在节点 c1 开始相交：

    在这里插入图片描述

    题目数据 保证 整个链式结构中不存在环。

    注意，函数返回结果后，链表必须 保持其原始结构 。
    在这里插入图片描述

    示例1：
    在这里插入图片描述
    输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
    输出：Intersected at '8'
    解释：
    相交节点的值为8(注意，如果两个链表相交则不能为 0)。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

    示例2：
    在这里插入图片描述
    输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
    输出：Intersected at '2'
    解释：
    相交节点的值为2(注意，如果两个链表相交则不能为 0)。从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

    提示：

    • listA 中节点数目为 m
    • listB 中节点数目为 n
    • 1 <= m, n <= 3 * 10^4
    • 1 <= Node.val <= 10^5
    • 0 <= skipA <= m
    • 0 <= skipB <= n
    • 如果 listA 和 listB 没有交点，intersectVal为 0
    • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

    思路一

    暴力求解，利用两个for循环依次比较链表 A、B 中的节点是否相同，如果相同就直接返回。如果循环结束都没有找到相同的节点，就返回NULL。这种方法是最容易想到的，但是时间复杂度为O(M*N)。

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    //暴力求解
    for(tailA = headA; tailA != NULL; tailA = tailA->next)
    {
        for(tailB = headB; tailB != NULL; tailB = tailB->next)
        {
            if(tailA == tailB)
                return tailA;
        }
    }
    return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    在这里插入图片描述

    思路二

    第二种思路比较用技巧性，时间复杂度也比较低，时间复杂度为O(M+N)。如果两条链表不相交，那么它们的尾节点一定不相同，返回NULL；而如果两条链表相交，那么它们的尾节点一定相同，返回第一个相交的节点。
    在这里插入图片描述

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    //计算链表A、B的长度
    int lenA = 1;
    while(tailA->next)
    {
        lenA++;
        tailA = tailA->next;
    }

    int lenB = 1;
    while(tailB->next)
    {
        lenB++;
        tailB = tailB->next;
    }

    //链表不相交，尾节点就不同
    if(tailA != tailB)
        return NULL;
    
    int gap = abs(lenA - lenB);//abs求lenA-lenB的绝对值，长度差
    //假设长的链表为A
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    //调整长链表
    if(lenA < lenB)
    {
        shortList = headA;
        longList = headB;
    }
    //长的先走差距步，然后一起走找第一个交点
    while(gap--)
    {
        longList = longList->next;
    }

    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    //返回交点
    return longList;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    在这里插入图片描述

    👉总结👈

    本篇博客讲解了四道经典的链表OJ题，其中涉及了链表的头插以及双指针的技巧。双指针的思想非常地重要，希望大家可以掌握。如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！💖💝❣️

  • 相关阅读:
    【信息奥赛实训】Week1——STL 与基础数据结构专题训练
    两种高效的事件处理模式：Reactor模式与Proactor模式
    十六、代码校验（5）
    机器学习复习（待更新）
    C# 连接mysql数据库ADO.NET模式， 数据绑定到datagridview控件上，设置部分列隐藏
    .NET/C#汇总 —— 常⻅的算法
    CUDA编程：矩阵乘运算从CPU到GPU
    HTTP相关知识
    Leetcode628：三个数的最大乘积
    Java实现自动发聊天消息
  • 原文地址：https://blog.csdn.net/m0_63639164/article/details/126399019