leetcode 147.对链表进行插入排序

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

⭐️ 题目描述

leetcode 147.对链表进行插入排序,刷题,leetcode,链表,学习
leetcode 147.对链表进行插入排序,刷题,leetcode,链表,学习

🌟 leetcode链接:对链表进行插入排序

思路与图解:
leetcode 147.对链表进行插入排序,刷题,leetcode,链表,学习
遍历链表,当前结点依次与前面的结点比较,选择插入位置。每次与前面的结点比较需要从头开始比较,所以定义一个 tempHead 指针,在定义一个 tempHeadPrev 指针记录 tempHead 前一个结点位置(方便插入),在定义一个 tail 记录前面区间的尾结点,当插入时需要考虑头插还是中间插入,当当前元素比前面区间元素都大时,说明无需插入当前位置合适,只需要改变 tail 指针(相当于确定新区间),下次继续迭代即可。

1️⃣ 代码:文章来源地址https://www.toymoban.com/news/detail-546574.html

struct ListNode* insertionSortList(struct ListNode* head){
	// 从第二个结点开始遍历链表
    struct ListNode* cur = head->next;
    // 记录前面区间的尾部
    struct ListNode* tail = head;
    while (cur) {
    	// 记录下遍历的下一个位置
        struct ListNode* next = cur->next;
        // 区间的头部
        struct ListNode* tempHead = head;
        // 区间头部的前一个结点
        struct ListNode* tempHeadPrev = NULL;
        // cur 依次和区间元素进行比较确认插入位置
        while (cur != tempHead && cur->val > tempHead->val) {
            tempHeadPrev = tempHead;
            tempHead = tempHead->next;
        }
        // 如果 cur 比 当前区间所有结点数据都大 更新尾区间
        if (cur == tempHead) {
            tail = cur; 
        }
        else {
        	// 插入
            if (tempHeadPrev == NULL) {
                // 头插入更新头指针
                head = cur;
            } else {
            	// 中间插入
                tempHeadPrev->next = cur;
            }
            tail->next = cur->next;
            cur->next = tempHead;
        }

        // 迭代
        cur = next;
    }

    return head;
}

到了这里,关于leetcode 147.对链表进行插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【leetcode刷题之路】初级算法(2)——链表+树+排序和搜索+动态规划

    3.1 【链表】删除链表中的节点 https://leetcode.cn/problems/delete-node-in-a-linked-list/ 给出的就是要删除的那个节点,直接前后移动就行了。 3.2 【双指针】删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/ 利用双指针left和right,首先让right遍历n个节点,再让两

    2024年02月10日
    浏览(51)
  • Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素

    思路:链表相关的问题建议就是画图去解决,虽然理解起来很容易,但就是写代码写不出来有时候,依次去遍历第二节点如果与前一个节点相等则跳过,不相等则遍历第三个节点

    2024年02月22日
    浏览(68)
  • leetcode算法刷题——链表

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 在链表类中实现这些功能: get(index):获取链表中第 index 个节点的值。如果索引无效,

    2024年02月21日
    浏览(48)
  • LeetCode刷题 --- 链表

    定义一个node节点 206 反转链表 题目:给你单链表的头节点  head  ,请你反转链表,并返回反转后的链表。 解题: 1、如果head为空或者只有一个节点,那么直接返回结果即可 2、否则,定义一个新链表,遍历旧链表,将每个节点插入到新链表的头部即可。 203 根据值来删除节点

    2024年02月05日
    浏览(37)
  • 【leetcode 力扣刷题】汇总区间//合并区间//插入区间

    题目链接:228.汇总区间 题目内容: 看题目真是没懂这个题到底是要干啥……实际上题目要求的 恰好覆盖数组中所有数字 的 最小有序 区间范围列表,这个最小是指一个区间范围小。比如能够覆盖{2,3,4,6}的区间可以是[2,6],但是5在区间内,却不在数组内,因此这个区间不是最

    2024年02月10日
    浏览(38)
  • Leetcode刷题之环形链表

    莫等闲,白了少年头,空悲切。                                            --岳飞 目录 1.环形链表 2.环形链表Ⅱ 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中

    2023年04月19日
    浏览(44)
  • leetcode刷题之回文链表

    目录 做题思路 代码实现 1.找到链表的中间节点 2.反转中间节点之后的链表 3.判断倒置的后半部分的链表是否等于前半部分的链表 整体代码展示 总结: 这里是题目链接。234. 回文链表 - 力扣(Leetcode)  这道题目的意思是:判断该链表中后半部分倒置是否跟前半部分相同,如

    2023年04月10日
    浏览(79)
  • LeetCode刷题(ACM模式)-02链表

    参考引用:代码随想录 注:每道 LeetCode 题目都使用 ACM 代码模式,可直接在本地运行,蓝色字体为题目超链接 0. 链表理论基础 0.1 链表定义 链表是一种 通过指针串联在一起的线性结构 ,每一个节点由两部分组成: 一个是数据域,一个是指针域 (存放指向下一个节点的指针

    2024年02月06日
    浏览(48)
  • 【LeetCode刷题-链表】--146.LRU缓存

    方法一:哈希表+双向链表 使用一个哈希表和一个双向链表维护所有在缓存中的键值对 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久使用的 哈希表即为普通的哈希映射,通过缓存数据的键映射到其在双向链表中的

    2024年02月05日
    浏览(46)
  • LeetCode 刷题 数据结构 链表 203 移除链表元素

    Given the  head  of a linked list and an integer  val , remove all the nodes of the linked list that has  Node.val == val , and return  the new head . Example 1: Example 2: Example 3: Constraints: The number of nodes in the list is in the range  [0, 104] . 1 = Node.val = 50 0 = val = 50 今天leetcode的中文官网比较卡,所以是登录官网进行

    2024年02月14日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包