• 【刷题系列】链表经典OJ题

    文章题目来源力扣或牛客
    🎈力扣（LeetCode）全球极客挚爱的技术成长平台
    LeetCode官网：https://leetcode-cn.com/problem-list/e8X3pBZi/
    牛客网-笔试题库：https://www.nowcoder.com

    在这里插入图片描述

    ✨目录

    1. 移除链表元素
    2. 反转链表
    3. 链表的中间节点
    4. 链表中倒数第k个结点
    5. 合并两个有序链表
    6. 链表分割
    7. 回文链表
    8. 相交链表
    9. 环形链表丨
    10. 环形链表II
    11. 复制带随机指针的链表

    1.移除链表元素

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/remove-linked-list-elements
    在这里插入图片描述

    • ✨思路一
      可以依次遍历链表，将不是val值的元素尾插到新的节点中
      时间复杂度：O(N)
      空间复杂度：O(1)
    struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode*newhead=NULL,*tail=NULL,*cur=head;
    while(cur)
    {
        if(cur->val!=val)//把不是val的尾插到newhead中
        {
            if(tail==NULL)
            {
                tail=newhead=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;    
            }
        }
        cur=cur->next;
    }
    //最后tail置空
    if(tail!=NULL)
    	tail->next=NULL;
    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
    • ✨思路二
      直接在原链表中删除，遇到val直接释放，让它的前一个指向val的后一个
      时间复杂度：O(N)
      空间复杂度：O(1)
    struct ListNode* removeElements(struct ListNode* head, int val){
    if(head==NULL)
    return NULL;


    struct ListNode*newNode=(struct ListNode*)malloc(sizeof(struct ListNode));//设置一个新的头结点
    newNode->next=head;
    struct ListNode*cur=newNode;
    while(cur->next)
    {
        if((cur->next)->val==val)//删val元素
        {
            struct ListNode *del=cur->next;
            cur->next=del->next;
            free(del);
        }
        else
        {
            cur=cur->next;
        }
    }
    cur=newNode->next;
    free(newNode);
    return cur;
}

    • 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

    在这里插入图片描述

    2.反转链表

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/reverse-linked-list
    在这里插入图片描述

    • ✨思路一
      依次遍历链表头插
      时间复杂度：O(N)
      空间复杂度：O(1)
    struct ListNode* reverseList(struct ListNode* head){

    //头插法
    struct ListNode* cur=head,*next=NULL,*newhead=NULL;
    while(cur)
    {
        next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • ✨思路二
      直接在原地修改指针指向
      时间复杂度：O(N)
      空间复杂度：O(1)
    struct ListNode* reverseList(struct ListNode* head){
    //原地修改
    struct ListNode*n1=NULL,*n2=head;
    while(n2)
    {
        struct ListNode*n3=n2->next;
        n2->next=n1;
        n1=n2;
        n2=n3;
    }
    return n1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这里插入图片描述

    3.链表的中间节点

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/middle-of-the-linked-list
    在这里插入图片描述

    • ✨思路一（不推荐）
      遍历一遍求出链表长度，长度除2后，再重新让指针走中间节点

    • ✨思路二（推荐）
      快慢指针法，定义两个指针，fast，slow，让fast一次走两步，slow一次走一步，fast走到NULL，slow就是中间节点

    struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*slow=head,*fast=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在这里插入图片描述

    4.链表中倒数第k个结点

    来源：牛客网
    链接：oj链接
    在这里插入图片描述

    • ✨思路
      有上题的铺垫，我们也可以用快慢指针，，定义两个指针，fast，slow，只不过这次先让fast走k步，然后fast和slow一起走，fast为NULL,slow就是倒数第K个节点
    struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    if(pListHead==NULL)
        return NULL;
    struct ListNode*fast=pListHead,*slow=pListHead;
    while(k--)//先让fast走k步
    {
    	//预防K很大，fast已经为空
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    //同时走
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

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

    在这里插入图片描述

    5.合并两个有序链表

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/merge-two-sorted-lists
    在这里插入图片描述

    • ✨思路
      依次遍历两个链表取小的尾插到新的头
      时间复杂度：O(N)
      空间复杂度：O(1)
    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

    struct ListNode*newhead=(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位
    newhead->next=NULL;
    struct ListNode*cur1=list1,*cur2=list2,*tail=newhead;
    while( cur1 && cur2 )//取小尾插
    {
        if(cur1->val  > cur2->val)
        {
            tail->next=cur2;
            cur2=cur2->next;
        }
        else
        {
            tail->next=cur1;
            cur1=cur1->next;
        }
        tail=tail->next;
    }
    if(cur1)//把剩下的连上
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }

    tail=newhead->next;
    free(newhead);
    return tail;
}

    • 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

    在这里插入图片描述

    6.链表分割

    来源：牛客网
    链接：OJ链接

    在这里插入图片描述

    • ✨思路
      遍历链表，把链表分成两条，一个全是小于x的，剩下的就是另一个链表，然后两个链表再拼接在一起

    在这里插入图片描述

        ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //设置两个哨兵位,head1存比x大的，head2存比x小的进行尾插
    struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode));
        head1->next=NULL,head2->next=NULL;
     struct ListNode* cur = pHead, * tail1 = head1, * tail2 = head2;
    while(cur)
    {
        if(cur->val < x)//取小的尾插到head2中
        {
            tail2->next=cur;
            tail2=tail2->next;
        }
        else//取大的尾插到head1中
        {
            tail1->next=cur;
            tail1=tail1->next;
        }
        cur=cur->next;
    }
        //将两部分连接，并将尾节点的next置空
        tail2->next=head1->next;
         tail1->next = NULL;
        pHead=head2->next;
        free(head1);
        free(head2);
        
        return pHead;
    }

    • 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

    在这里插入图片描述

    7.回文链表

    来源：牛客网
    链接：OJ链接

    在这里插入图片描述

    • ✨思路
      先找到中间节点，把后半部分逆置，然后再依次比较是否相等
    struct ListNode* reverseList(struct ListNode* head){

    struct ListNode*n1=NULL,*n2=head;
    while(n2)
    {
        struct ListNode*n3=n2->next;
        n2->next=n1;
        n1=n2;
        n2=n3;
    }
    return n1;
}
    struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*slow=head,*fast=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid=middleNode(A);//找中间节点
        struct ListNode*cur2=reverseList(mid);//从中间节点开始逆置
        struct ListNode*cur1=A;
        while(cur2)//依次比较
        {
            if(cur1->val!=cur2->val)
                return false;
            cur2=cur2->next;
            cur1=cur1->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

    在这里插入图片描述

    8.相交链表

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/intersection-of-two-linked-lists

    在这里插入图片描述

    • ✨思路
      仔细观察可以发现，如果链表相交的话，那么它们都有一个共同的特点，那就是尾节点相同，所以可以利用这个特点来解决链表是否相交
      至于返回相交点，我们可以依次算出每一个链表的长度，然后让长的那个一个先走差距步，然后再同时走，直到相等即为相交点

    在这里插入图片描述

    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

    struct ListNode* cur1=headA,*cur2=headB;
    int count1=1,count2=1;
    //找尾
    while(cur1->next)
    {
        cur1=cur1->next;
        count1++;
    }
    while(cur2->next)
    {
        cur2=cur2->next;
        count2++;
    }
    //尾节点不相等则不相交
    if(cur1!=cur2)
        return NULL;

    struct ListNode*longList=headA,*shotList=headB;
    if(count1 < count2 )
    {
        longList=headB;
        shotList=headA;
    }
    int k=abs(count1-count2);
    //让长的先走差距步
    while(k--)
    {
        longList=longList->next;
    }
    //相等地方即为入口
    while(longList!=shotList)
    {
        longList=longList->next;
        shotList=shotList->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

    在这里插入图片描述

    9.环形链表丨

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/linked-list-cycle

    在这里插入图片描述

    • ✨思路
      快慢指针法：定义两个指针fast和slow，fast一次走两步，slow一次走一步，最后如果相等则说明存在环，如果fast遇到NULL，则说明没有环
      证明：
      在这里插入图片描述
    bool hasCycle(struct ListNode *head) {
    struct ListNode*fast,*slow;
    fast=slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
            return true;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    在这里插入图片描述

    10.环形链表 II

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/linked-list-cycle-ii
    在这里插入图片描述

    • ✨思路一
      快慢指针法：定义两个指针fast和slow，fast一次走两步，slow一次走一步，相等位置为相遇点，在相遇点断开，转化成两个链表相交求交点问题

    在这里插入图片描述

    • ✨思路二
      这个解法很妙，就是从找到相遇点后，一个指针从相遇点开始，另一个指针从头开始，同时遍历，直到相等就是入环点，这个可以用数学公式证明

    在这里插入图片描述

    //思路二的代码实现
struct ListNode *detectCycle(struct ListNode *head) {
        struct ListNode*fast,*slow;
    fast=slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)//有环
        {
            struct ListNode*cur=head;
            while(cur!=slow)//入口点
            {
                cur=cur->next;
                slow=slow->next;
            }
            return cur; 
        }
    }
     return NULL;

}

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

    在这里插入图片描述

    11.复制带随机指针的链表

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/copy-list-with-random-pointer
    在这里插入图片描述

    • ✨思路
      这题主要的难点在于随机指针random的复制，搞定了这个随机指针，那么问题就迎刃而解了
      首先，我们可以把每一个复制节点的尾插到每一个原节点的后面，然后依次根据原节点的random把复制节点的random连接上，最后再恢复原链表，取复制链表

    在这里插入图片描述

    struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head,*next=head,*copy=NULL;
    //复制节点尾插到原节点中
    while(cur)
    {
        next=cur->next;
        copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        cur->next=copy;
        copy->next=next;
        
        //迭代
        cur=next;
    }
	//复制randam
    cur=head;
    while(cur)
    {
        copy=cur->next;
        next=cur->next->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        //迭代
        cur=next;
    }

    //恢复原链表
    struct Node*copyhead=NULL,*tail=NULL;
    cur=head;
    while(cur)
    {
        copy=cur->next;
        next=cur->next->next;
        if(copyhead==NULL)
        {
            copyhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur->next=next;
        //迭代
        cur=next;
    }
    return copyhead;
}

    • 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

    在这里插入图片描述

  • 相关阅读:
    mybatis代理
    JavaScript入门
    浅学Python入门
    Mac M1采用docker安装工具
    4.使用CFileDialog打开文件对话框,获得文件路径 -windows编程
    阿里云linux服务器：能ping通但是无法访问tomcat
    [计算机提升] Windows文件系统类型介绍
    算法落地思考：如何让智能运维更智能
    python实例代码介绍python基础知识
    Chrome下载离线安装包进行安装
  • 原文地址：https://blog.csdn.net/dongming8886/article/details/126184047