顺序表链表OJ题(1)——【LeetCode】

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

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

W...Y的主页 😊

代码仓库分享 💕


 前言:

今天我们来回顾一下顺序表与链表,针对这一块我们也有许多OJ题目供大家参考。当我们学习完顺序表链表后避免不了一些习题的练习,这样才能巩固我们学习的内容。

话不多说,我们开始进入OJ习题训练!!!

【leetcode 27.移除元素】 

OJ链接

给你一个数组 和一个值 ,你需要原地移除所有数值等于 的元素,并返回移除后数组的新长度。numsvalval

不要使用额外的数组空间,你必须仅使用 额外空间并原地修改输入数组O(1)

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

题目函数接口顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言 nums:给定数组内容。numsSize:数组长度大小。val:移除元素。


题目要求原地删除数据,不能创建任何数组,这就会使原本简单的题变复杂。那我们应该怎么办呢?

首先我们最先想到的方法是遍历数组,遇到需要删除的内容就将数组后面的元素向前挪动一位,让其覆盖。但是这种方法非常”危险“,有可能导致数组越界,也有可能删除遗漏。所以这不是个好方法。

接下来将一个比较新颖且简单的方法:

双指针: 创建两个指针变量src与dst,两个指针全部指向数组开头。如果src指向的内容不是val,将src的内容赋值给dst,然后src与dst全部向后挪动一位。反之如果src指向的内容为val,dst保持原来的位置不动,src向后挪动一位。直至src指向数组的末尾结束。顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

 这个方法即保证没有创建任何数组空间复杂度为O(1),也优化了暴力遍历法中时间复杂度,从O(n^2)->O(n)。

代码展示:

nt removeElement(int* nums, int numsSize, int val){

    int ret = 0;
    int valp = 0;
    int n = numsSize;
    while(ret < numsSize)
    {
       
        if(nums[ret] != val)
        {
           nums[valp++] = nums[ret++];
        }
        else
            ret++;

    }
    return valp;
}

【leetcode 26.删除有序数组中的重复项】

OJ链接 

给你一个 升序排列 的数组 nums ,请你原地删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过,那么您的题解将被通过

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

题目函数接口:顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言 nums:升序数组。numsSize:数组中元素个数。


思路:快慢双指针

分析:创建两个指针变量fast与slow顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

如果两个指针指向内容全部相同,fast向后挪动一位slow不变。

如果两个指针指向不同内容,先让slow向后移动一位,再将fast指向的内容赋值给slow,再将fast向后移动一位即可。

等到fast指向数组末尾时,循环结束!

代码演示: 

int removeDuplicates(int* nums, int numsSize){
    int fast = 1;
    int slow = 0;
    int n = numsSize;
    while(fast < n)
    {
        if(nums[fast] != nums[slow])
        {
            slow++;
            nums[slow] = nums[fast];
        }
        else
        {

           fast++;
        }
        
    }
    return slow+1;

}

leetcode 88.合并两个有序数组】 

OJ链接

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

题目接口函数: 

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

nums1与nums2:两个非递减数组。nums1Size:nums1数组大小。nums2Size:nums2数组大小。m:nums1数组有效元素个数。n:nums2数组有效元素个数。


其实我们可以直接将两个数组进行归并,然后进行qsort排序直接完成。但是效率太低了,qsort函数底层原理为快速排序法,时间复杂度太高。

那有没有什么时间复杂度低的解法呢?

这道题本来可以两个数组进行比较,再开辟一个数组,两个数组元素进行比较,谁比较小就尾插到新数组中去。

但是这个题比较特殊,nums1开辟的空间比较大,可以放下两个数组的所有内容,所以我们必须将排序好的数组放入nums1中为了保证时间复杂度为O(m+n)。

但是我们可以使用这种方法的变形(三指针)。

解法:我们可以倒着比较,取大的依次从后往前插入。 创建三个指针,一个指向nums2数组末尾处,一个指向nums1有效元素末尾,还有一个指向nums1数组末尾处。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

然后我们进行比较即可:顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言 注意当end1与end2全部结束才可以结束循环,否则会有问题。

举例:num1:【5,6,7,0,0,0】,num2:【2,5,6】

 代码展示:



void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
      int end1 = m-1, end2 = n-1, end = m+n-1;
    while(end1 >= 0 && end2 >= 0){
        if(nums1[end1] > nums2[end2])
            nums1[end--] = nums1[end1--];
        else
            nums1[end--] = nums2[end2--];
    }
    while(end2 >= 0)
        nums1[end--] = nums2[end2--];

}

【leetcode 206.反转链表】

OJ链接

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

 题目接口函数:

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

head:链表头节点


我们在反转数组时,只需要两个指针一个指向头,一个指向尾进行交换即可,最后指向中间即可结束。但是单链表没有数组的特性,不能进行逆向读取,所以这个方法行不通。

现在提供两种方法:

方法一:创建3个指针n1、n2、n3分别指向NULL、head、head->next。标记好三个位置即可进行链表反转。顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言 让n2->next指向n1,然后n1=n2、n2=n3、n3=n3->next即可顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

一直循环直到n3指向NULL时循环停止结束。

代码演示: 

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* a = NULL;
    struct ListNode* b = head;
    struct ListNode* c = NULL;
    if(b)
    c = b->next;
    if(head)
    {
        while(c)
        {
            a = b;
            b = c;
            c = b->next;
            b->next = a;
        
        }
        head->next = NULL;
        return b;
    }
    else
        return head;

 我们考虑问题就必须全面,如果链表中只有一个数则返回头指针head即可。

(头插法)方法二:

创建一个新链表头newhead,将旧链表元素挨个反向插入newhead中即可。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言 

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

上述就是操作流程图!!!

代码演示:

struct ListNode* reverseList(struct ListNode* head){ 
struct ListNode* cur = head;
    struct ListNode*  newhead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;

        newhead = cur;
        cur = next;
    }
    return newhead;

}

【leetcode 203.移除链表元素】

OJ链接

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

 题目接口函数:

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

head:链表头节点。val:删除目标数


思路分析:移除目标元素,我们就要遍历链表进行查找。创建两个指针prev与cur,prev永远指向cur前一个节点,用来记录。

当cur遇到目标数时,我们就可以使用prev->next =cur->next,将目标数删除。直至cur指向NULL结束。

整体思路如下:

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言 虽然看上去很简单,但是这种题的“极端”情况非常多。我们必须把这些特殊情况考虑清楚再去写程序才能保证万无一失。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

如果遇到上述情况,使用prev->next =cur->next就不实用了,程序就会出错。那我们应该怎么办呢?

我们应该在使用prev->next =cur->next时就先把元素为val的干掉,让head指向不是val的元素。顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言 下面是代码演示:

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* prev = NULL, *cur = head;
    while(cur)
    {
        if(cur->val == val)
        {
            if(cur == head)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

还有一种思路更清晰的方法:

创建一个新的头节点newhead,让cur遍历链表,把元素内容不是val的挪下来与newhead链接即可。顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

这样的思路更清晰,空间复杂度对于之前方法一没有改变,但是时间复杂度增加了。因为在newhead尾插时要找尾节点。我们可以增加一个尾指针指向newhead链表的尾节点,这样就可以优化时间复杂度。

代码演示:

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL, *tail = NULL;
    while(cur)
    {
        if(cur->val == val)
        {
            struct ListNode*der = cur;
            cur = cur->next;
            free(der);
        }
        else{
            if(tail == NULL)
            {
                newhead = tail = cur;
            }
            else{
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        if(tail)
        {
            tail->next = NULL;
        }
    }
    return newhead;
}

 代码中有很多极端问题需要大家去想清楚,在这里就不过多讲述了,不懂可以私信我!!!

【leetcode 876.链表的中间节点】

OJ链接 

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

题目函数接口:

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

head:目标链表的头节点。


分析题目:这道题我们可以使用最原始的方法进行,先将链表遍历一遍求出链表长度,然后再次进行循环找出中间值即可。

但是有些公司面试会有题目限制要求,只让我们遍历一遍找出中间值。那我们应该怎么做呢?

(快慢指针):

我们创建两个指针变量slow与fast指向链表的头节点,slow一次只移动一个节点,而fast指针一次移动两个节点。当fast指向NULL时,我们的slow节点顺理成章的就找到了中间节点。

顺序表链表OJ题(1)——【LeetCode】,链表,数据结构,算法,c语言

这种类型的题目我们就可以利用速度差来达到题目要求!

代码演示: 

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

以上是本次全部内容,有错误或不同见解的希望与博主进行沟通交流,博主会继续努力将更好的博客内容带给大家,你们的三连是对博主最大的支持!!! ❤️❤️文章来源地址https://www.toymoban.com/news/detail-685214.html

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

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

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

相关文章

  • 数据结构:带环单链表基础OJ练习笔记(leetcode142. 环形链表 II)(leetcode三题大串烧)

    目录 一.前言  二.leetcode160. 相交链表  1.问题描述 2.问题分析与求解 三.leetcode141. 环形链表 1.问题描述 2.代码思路  3.证明分析  下一题会用到的重要小结论: 四.leetcode142. 环形链表 II 1.问题描述 2.问题分析与求解 Judgecycle接口: 方法一: 方法二:  单链表和带环单链表

    2023年04月08日
    浏览(40)
  • 数据结构——链表OJ题

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

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

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

    2024年02月05日
    浏览(51)
  • 【数据结构OJ题】环形链表

    原题链接:https://leetcode.cn/problems/linked-list-cycle/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 整体思路: 定义 快慢指针fast,slow ,如果 链表确实有环 , fast指针一定会在环内追上slow指针。 即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,

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

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

    2024年02月04日
    浏览(65)
  • 【数据结构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日
    浏览(44)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(72)
  • 【数据结构OJ题】环形链表II

    原题链接:https://leetcode.cn/problems/linked-list-cycle-ii/description/ 如果有小伙伴不了解环形链表,可以先看看这篇文章: https://blog.csdn.net/m0_62531913/article/details/132352203?spm=1001.2014.3001.5502 我们来看下图:  我们根据这个结论就可以做出这道题目了!

    2024年02月12日
    浏览(44)
  • 【数据结构与算法】手撕链表OJ题

    给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 思路一 :一种比较普遍的方式,边遍历边找不同。我们可以通过定义两个指针,一个指向头节点,一个置为NULL。当遇到值为相同的时候,直接跳过去。指向下一位

    2024年02月10日
    浏览(45)
  • 【数据结构OJ题】移除链表元素

    原题链接:力扣  给你一个链表的头节点  head  和一个整数  val  ,请你删除链表中所有满足  Node.val == val  的节点,并返回 新的头节点  。  方法一:原地删除节点 思路:  首先,定义两个指针:prve和cur。它们会在遍历链表的过程中分别指向当前节点的前一个节点和当前

    2024年02月11日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包