力扣练习——链表在线OJ

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

目录

提示:

一、移除链表元素

题目:

解答:

二、反转链表

题目:

解答:

三、找到链表的中间结点

题目:

解答:

四、合并两个有序链表(经典)

题目:

解答:


提示:

①:接上一篇文章

本次我们来做一些在线OJ题,进一步加深印象和感觉,并且本次某些方法会沿用上一篇文章的,所以感兴趣的小伙伴可以参考一下上一篇文章。

②:对于这些在线OJ,小编会把具体步骤放在注释里面,然后小编没有画图,大家可自行画图然后跟着解析思路一起思考。

③:链表的在线OJ一般都是用的无哨兵的头指针,所以大家一定要搞懂有哨兵和无哨兵的区别。

一、移除链表元素

题目:

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

解答:

思路:只需要一边遍历链表,一边进行数据域的比较。若找到指定的值val,则删除该结点;

又因为删除一个结点,我们必须知道该结点的前一个结点,所以采用双指针的思路:

一个指针prve用于记录指定结点的前一个结点;

一个指针cur用于遍历寻找。

另外,找的过程中会发生两种情况;

情况一:指定结点为头结点(即头指针的位置):这时我们需要考虑头指针head的变化,具体实现看注释;

情况二:指定结点为一般结点:这时我们就依靠前一个结点正常删除即可;

源代码即注释如下:
 

struct ListNode* removeElements(struct ListNode* head, int val) 
{
	//双指针prev、cur
	struct ListNode* prev = NULL, *cur = head;
	//当cur==NULL。即过了尾结点,遍历完成,退出循环
	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;
}

二、反转链表

题目:

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

解答:

思路:我们可以将当前结点的next域指向前一结点,但在此之前我们应该把当前结点的前一个结点和后一个结点给保存下来,防止结点丢失;

所以我们可以创建两个临时指针prve和cur;

cur用于保存下一个结点;

prve用于保存前一个结点;

而头结点head就用于保存当前结点;

struct ListNode* reverseList(struct ListNode* head) 
{
	//两个临时指针
	struct ListNode* cur = head, * prve = NULL;
	//因为cur是用于保存下一个结点,所以当cur为空时,即遍历完链表,循环结束
	while (cur)
	{
		//cur保存下一个结点
		cur = cur->next;
		//将当前结点的next域指向前一个结点
		head->next = prve;
		//将prve保存当前结点,也就是保存下一轮操作的"前一个结点"
		prve = head;
		//完成一轮操作,head重定位当前结点
		head = cur;
	}
	//最后当head和cur都为NULL时,prve作为前一个结点即为"原链表的尾结点,反转链表的首结点”,所以返回prve
	return prve;
}

三、找到链表的中间结点

题目:

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

解答:

这道题用到一个经典思路叫:“快慢指针”;

即定义两个指针;

一个快指针fast,一次向后跳过两个结点;

一个慢指针slow,一次向后跳过一个结点;

初略想一下,当fast指针遍历完数组后,solw指针就是我们想要的中间结点;

但这里要分奇数个结点还是偶数个结点,如下:

奇数个结点的情况:

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

偶数个结点的情况:

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

所以结束有两个可能,即快指针指向尾结点或者快指针指向NULL;

struct ListNode* middleNode(struct ListNode* head) 
{
    //快指针fast,慢指针slow
    struct ListNode* fast = head, * slow = head;
    //因为不确定奇数个还是偶数个,所以当快指针任意满足一种情况,则结束
    while (fast && fast->next)
    {
        //慢指针走一步
        slow = slow->next;
        //快指针走两步
        fast = fast->next->next;
    }
    return slow;
}

四、合并两个有序链表(经典)

题目:

力扣练习——链表在线OJ,LeetCode,数据结构与算法,leetcode,链表,算法

解答:

①:由合并升序链表,我们可以联想到合并升序顺序表(数组),我们知道是将大的一个数放在大空间的末尾,第二大的数放在大空间的倒数第二个位置,重复此操作,直到短的一方比较完,再把长的一方剩下的元素连接在末尾;

②:但链表和顺序表有一点区别是,链表只需要逻辑上相邻即可;

③:所以我们可以创建两个临时指针:

一个临时指针head用于充当新合并链表的头指针;

一个临时指针tail用于插入操作;

④:具体我们只需要将两个链表中的元素依次比较,再将数据域小的结点尾插到tail链表后面,因为tail和head指向同一个链表,只是head是头指针,过程中是tail再变,所以要注意tail指针的变化,最后返回head头指针即可。

⑤:其中我们可能遇到三种情况:

情况一、链表一或链表二为空,则直接返回另一个链表;

情况二、链表一和链表二长度相等,则循环上述操作;

情况三、长度不相等,则操作到某一时刻,链表一或二就会为NULL,这时就会出循环,然后再将长的链表剩下的元素插到tail结点后面。

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    //情况一、表一或表二为NULL,直接返回另一个表
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    //情况二、按正常操作来进行
    struct ListNode* head = NULL, * tail = NULL;
    while (list1 && list2)
    {
        //依次比较数据域
        if (list1->val < list2->val)
        {
            //第一次需要将head和tail指针指向首结点较小的表,以便后续能尾插结点
            if (tail == NULL)
            {
                head = tail = list1;
            }
            //尾插
            else
            {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
        else
        {
            //第一次需要将head和tail指针指向首结点较小的表,以便后续能尾插结点
            if (tail == NULL)
            {
                head = tail = list2;
            }
            //尾插
            else
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    //情况三、两个表长度不相等,会有一个表有剩余
    //因为是升序表,所以直接将剩余的表插入tail的next域即可
    if (list1)
    {
        tail->next = list1;
    }
    if (list2)
    {
        tail->next = list2;
    }
    //最后返回合并的表的头指针
    return head;
}

本次知识到此结束,希望对你有所帮助!文章来源地址https://www.toymoban.com/news/detail-721431.html

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

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

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

相关文章

  • 数据结构:力扣OJ题

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

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

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

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

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

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

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

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

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

    2024年02月05日
    浏览(47)
  • 数据结构——二叉树(OJ练习)

    大家好,本期是二叉树的最后一期,这一期我们来看看二叉树的编程题 . - 力扣(LeetCode) 首先我们的思路是: 遍历二叉树,把每个节点去比较一次,按照要求返回 我们来看代码 . - 力扣(LeetCode) 这里我们的思路是:同时遍历两给树,遇到空树或者不相等时返回。 . - 力扣

    2024年04月12日
    浏览(42)
  • 数据结构——图解链表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)
  • 【数据结构OJ题】环形链表

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

    2024年02月12日
    浏览(40)
  • 数据结构刷题训练:设计循环队列(力扣OJ)

    目录 文章目录 前言 1. 题目:设计循环队列 2. 思路 3. 分析  3.1 定义循环队列  3.2 创建队列  3.3 判空和判满  3.4 入队  3.5 出队  3.6 取队头队尾数据  3.7 销毁队列  4. 题解 总结         当谈到队列数据结构时,很多人可能会想到普通的队列,即先进先出(FIFO)的数据结

    2024年02月13日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包