【OJ】链表刷题

这篇具有很好参考价值的文章主要介绍了【OJ】链表刷题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页 : zxctsclrjjjcph
文章封面来自:艺术家–贤海林
如有转载请先通知

1. 相交链表(160)

【OJ】链表刷题,OJ题,链表,数据结构,力扣
【OJ】链表刷题,OJ题,链表,数据结构,力扣
【OJ】链表刷题,OJ题,链表,数据结构,力扣

1.1 暴力求解

1.1.1 分析

题目中描述既要判断是否相交,还要找交点。
把A链表中的所有节点依次在B中找一边。
为了防止在遍历链表时头节点丢失,先记录一下AB头节点:

    struct ListNode* begin1 = headA;
    struct ListNode* begin2 = headB;

先取A的节点,在B链表中遍历一遍,判断B中节点与A是否相交,如果相交,直接返回A的节点,如果不相交,B节点继续往后走。
【OJ】链表刷题,OJ题,链表,数据结构,力扣
当A的第一个节点在B中没有找到相交时,A节点就往后走,继续像第一个节点判断方式一样。不过这里得注意一下,再次访问B链表时候,B的走的节点又得从头节点开始begin2 = headB
当A链表中所有节点都访问完了后,B都没有与之相交的,就返回NULL

1.1.2 代码实现

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* begin1 = headA;
    struct ListNode* begin2 = headB;
    while (begin1)
    {
        begin2 = headB;
        while (begin2)
        {
            if (begin1 == begin2)
                return begin1;
            begin2 = begin2->next;
        }
        begin1 = begin1->next;
    }
    return NULL;
}

【OJ】链表刷题,OJ题,链表,数据结构,力扣

1.2 优化后求解

暴力求解虽然简单,但是时间复杂度太高为O(n^2),优化一下代码,使得时间复杂度到O(n)。

1.2.1 分析

可以先判断是否相交,如果A和B两个链表的尾节点的地址都相同,那么就A和B两个链表相交。如果如果A和B两个链表的尾节点的地址不相同,那么就A和B两个链表不相交。
如果相交那么交点怎么求呢?
先求出A和B两个链表的长度,

  while(begin1->next)
   {
        lenA++;
        begin1=begin1->next;
   } 

   while(begin2->next)
   { 
        lenB++;
        begin2=begin2->next;
    }

让长的链表先走两个链表相查的节点数,

    while(n--)
    {
        longlist=longlist->next;
    }

两个链表再同时走,第一个相同的就是交点。

    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;

1.2.2 代码实现

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   struct ListNode *begin1=headA;
   struct ListNode *begin2=headB;
   int lenA=1;
   int lenB=1;
   while(begin1->next)
   {
        lenA++;
        begin1=begin1->next;
   } 

   while(begin2->next)
   { 
        lenB++;
        begin2=begin2->next;
    }
    if(begin1!=begin2)
    {
        return NULL;
    }

    int n=abs(lenA-lenB);
    struct ListNode *longlist=headA;
    struct ListNode *shortlist=headB;
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }
    
    while(n--)
    {
        longlist=longlist->next;
    }

     while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}

【OJ】链表刷题,OJ题,链表,数据结构,力扣

2. 随机链表的复制(138)

【OJ】链表刷题,OJ题,链表,数据结构,力扣

2.1 分析

这里链表里面包含单链表和随机指针,而随机指针指向链表任意节点或者为空。
【OJ】链表刷题,OJ题,链表,数据结构,力扣

对于节点的拷贝就是申请节点放原节点值任何尾插就行,复制链表倒是容易的。这里主要就是考虑随机指针怎么处理。
如果记录值让随机指针指向,可能会有多个相同的值。所以这里可以记录这个random出现的位置,看看是第几个用i记录,这样就不会出现多个随机指针指向同一个节点。如果每次复制节点都要找第i个,每个找random都是N,那么时间复杂度就是O(N^2)。时间复杂度太高了,优化一下。
【OJ】链表刷题,OJ题,链表,数据结构,力扣
第一步:可以把拷贝的节点都放在原节点的后面,也就是这样:
【OJ】链表刷题,OJ题,链表,数据结构,力扣

这样能方便找到原节点与random的关系。

    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        copy->next=cur->next;
        cur->next=copy;
        
        cur=copy->next;
    }

【OJ】链表刷题,OJ题,链表,数据结构,力扣
第二步:处理copy节点的random。
再从头开始走第二遍,copy节点每次都等于cur节点的next。
如果cur的random为空,copy节点的random也为空。
如果不是空,copy的random就是cur的random的next。

    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
       cur=copy->next;  
    }

【OJ】链表刷题,OJ题,链表,数据结构,力扣
第三步:copy节点解下来尾插
出现申请一个新头节点,任何将copy节点一个一个取下来尾插,最后返回新的头节点。

    struct Node* newhead=NULL,*tail=NULL;
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(tail==NULL)
        {
            newhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur->next=next;
        cur=next;
    }
    return newhead;

2.2 代码实现

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        copy->next=cur->next;
        cur->next=copy;

        cur=copy->next;
    }

    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
       cur=copy->next;  
    }

    struct Node* newhead=NULL,*tail=NULL;
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(tail==NULL)
        {
            newhead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur->next=next;
        cur=next;
    }
    return newhead;
}

【OJ】链表刷题,OJ题,链表,数据结构,力扣
有问题请指出,大家一起进步!文章来源地址https://www.toymoban.com/news/detail-805094.html

到了这里,关于【OJ】链表刷题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 趣说数据结构(练习2) —— 顺序表/链表力扣刷题(中等难度)

    力扣原题:https://leetcode.cn/problems/reverse-linked-list-ii/ 题目描述 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left = right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 示例 1 输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5] 示例 2 输入:h

    2024年02月01日
    浏览(45)
  • 数据结构刷题篇 之 【力扣二叉树基础OJ】详细讲解(含每道题链接及递归图解)

    有没有一起拼用银行卡的,取钱的时候我用,存钱的时候你用 难度等级:⭐ 直达链接:相同的树 难度等级:⭐ 直达链接:单值二叉树 难度等级:⭐⭐ 直达链接:对称二叉树 难度等级:⭐⭐⭐ 直达链接:二叉树的前序遍历 难度等级:⭐⭐⭐⭐ 直达链接:另一颗子树 注:

    2024年04月16日
    浏览(78)
  • 数据结构:力扣OJ题

    目录 ​编辑题一:链表分割 思路一: 题二:相交链表 思路一: 题三:环形链表  思路一: 题四:链表的回文结构 思路一: 链表反转: 查找中间节点: 本人实力有限可能对一些地方解释的不够清晰,可以自己尝试读代码,望海涵! 现有一链表的头指针 ListNode*  pHead ,给

    2024年02月13日
    浏览(41)
  • 【数据结构刷题】数组oj

    题目: https://leetcode.cn/problems/remove-element/ 写一段原地移除数组中所有的元素val,要求时间复杂度为O(N^2),空间复杂度为O(1)的代码实现: 思路:遇到这个val后面的元素往前面覆盖。 int main() { int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int val = 2; 写一段原地移

    2024年02月14日
    浏览(31)
  • 数据结构——链表OJ题

    目录   1.给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 3.变形题:找到链表中倒数第k个

    2024年02月21日
    浏览(39)
  • 数据结构:力扣OJ题(每日一练)

    目录 题一:环形链表 思路一: 题二:复制带随机指针的链表  思路一: 本人实力有限可能对一些地方解释的不够清晰,可以自己尝试读代码,望海涵! 给定一个链表的头节点   head  ,返回链表开始入环的第一个节点。  如果链表无环,则返回  null 。 如果链表中有某个节

    2024年02月12日
    浏览(43)
  • 数据结构:力扣OJ题(每日一练)

    示例:         初始化: 初始化队列Q1,Q2; 入栈: 先将要入栈的数据放入为空的队列中,都为空时,放入Q1; 出栈: 当要出栈时,将Q1的数据出列n-1个,此时的Q1就是栈要出栈的数据(每次出栈都进行一次第三步将为不为空的队列数据放n-1个到为空队列中)); 获取栈顶元

    2024年02月12日
    浏览(41)
  • 【数据结构初阶】链表OJ

    OJ 方案一: 题目解析: 方案二: 题目解析:把原链表遍历一遍,插入新链表 OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: 定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交 OJ 题目解析: OJ 题目解析:

    2024年02月05日
    浏览(47)
  • 数据结构——图解链表OJ题目

            学完了单链表之后,我们对其基本结构已经有了一定的了解,接下来我们通过一些题目强化对链表的理解,同时学习一些面试笔试题目的新思路以及加强对数据结构单链表的掌握。  目录 题目一.876. 链表的中间结点 - 力扣(LeetCode) 题目二:21. 合并两个有序链表

    2024年02月04日
    浏览(62)
  • 【数据结构OJ题】链表分割

    原题链接:https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8tqId=11004rp=2ru=/activity/ojqru=/ta/cracking-the-coding-interview/question-ranking 目录 1. 题目描述 2. 思路分析 3. 代码实现 整体思路: 创建两个链表 ,分别存放 小于x的结点 和 大于等于x的结点 , 分别进行尾插 。 这道题目使

    2024年02月12日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包