首页 > 其他分享 >LeetCode //C - 147. Insertion Sort List

LeetCode //C - 147. Insertion Sort List

时间:2024-06-02 20:00:44浏览次数:26  
标签:Sort 147 head ListNode struct List list next sorted

147. Insertion Sort List

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list’s head.

The steps of the insertion sort algorithm:

  1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
  3. It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.
在这里插入图片描述
 

Example 1:

在这里插入图片描述

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

在这里插入图片描述

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Constraints:
  • The number of nodes in the list is in the range [1, 5000].
  • -5000 <= Node.val <= 5000

From: LeetCode
Link: 147. Insertion Sort List


Solution:

Ideas:

1. Node Definition and Creation:

  • The ListNode structure defines a node in a singly linked list.
  • The createNode function creates a new node with a given value.

2. Insertion Sort Function:

  • The insertionSortList function sorts the linked list using the insertion sort algorithm.
  • It iterates through each node in the original list, and inserts it into the correct position in the sorted list.

3. Helper Function:

  • The printList function is used to print the values of the linked list nodes.
Code:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

struct ListNode* insertionSortList(struct ListNode* head) {
    if (!head) return NULL;
    
    struct ListNode* sorted = NULL;
    
    while (head) {
        struct ListNode* current = head;
        head = head->next;
        
        if (!sorted || sorted->val >= current->val) {
            current->next = sorted;
            sorted = current;
        } else {
            struct ListNode* temp = sorted;
            while (temp->next && temp->next->val < current->val) {
                temp = temp->next;
            }
            current->next = temp->next;
            temp->next = current;
        }
    }
    
    return sorted;
}

// Function to print the linked list
void printList(struct ListNode* head) {
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

标签:Sort,147,head,ListNode,struct,List,list,next,sorted
From: https://blog.csdn.net/navicheung/article/details/139396144

相关文章

  • 集合类源码浅析のArrayList
    源码分析路线图:初级部分:ArrayList->LinkedList->Vector->HashMap(红黑树数据结构,如何翻转,变色,手写红黑树)->ConcurrentHashMap中级部分:Spring->SpringMVC->SpringBoot->Mybatis核心类源码高级部分:中间件源码(有生之年系列)第一篇,从最简单的ArrayList入手分析1、成员变量......
  • 如何轻松实现两个List的高效交集操作
    哈喽,大家好,我是木头左!一、引言在编程的世界里,总是在寻找更高效、更简洁的方法来解决问题。今天,将探讨如何在Java中轻松实现两个List的交集操作,让你的代码更加简洁、高效。二、JavaList简介让了解一下Java中的List接口。List是一个有序的集合,可以包含重复的元素。它提供了一......
  • ListView超强总结
        ListView由于手机屏幕空间都比较有限,能够一次性在屏幕上显示的内容并不多,当我们的程序中有少量的数据需要展示的时候,就可以借助ListView来实现。ListView允许用户通过手指上下滑动的方式将屏幕外的数据滚动到屏幕内,同时屏幕上原有的数据则会滚动出屏幕。相信你......
  • CentOS Linux 8x 错误:为仓库 ‘appstream‘ 下载元数据失败 : Cannot prepare interna
    问题描述今天安装CentOS8.5安装完之后,准备更新源仓库环境的时候突然出现错误:为仓库'appstream'下载元数据失败:Cannotprepareinternalmirrorlist:NoURLsinmirrorlist,后面我找了好久没发现有解决这个问题的方法,后面无意看到了https://www.cnblogs.com/cainiaoaixuexi......
  • Python教程-快速入门基础必看课程05-List索引
    摘要该视频主要讲述了Python中列表的基本操作,包括创建、添加元素、查找特定值、计算元素数量以及获取最后一个元素等。视频以清晰的例子和解释来展示这些操作,非常有助于初学者理解。此外,视频还讲述了Python中索引和切片的使用方法,这些是Python中非常重要的基础概念。掌握这些......
  • MyBatis的XML配置:如何判断List为空并遍历拼接
    哈喽,大家好,我是木头左!大家好,欢迎来到我的博客!今天要聊一聊关于MyBatis的XML配置,如何在查询数据表时判断List是否为空,并进行遍历拼接。相信这个问题对于很多使用MyBatis的朋友来说都非常实用,所以请大家认真阅读哦!一、为什么需要判断List是否为空?在的日常开发中,经常会遇到需要......
  • java数据list写入文件
    /***生成数据文件**@paramdata数据*@paramfileName文件名*@return数据文件对象*@throwsIOException*/privateFilegenerateDataFile(List<List<String>>data,StringfileName)throwsIOException{......
  • ### Cause: java.sql.SQLSyntaxErrorException: Expression #4 of SELECT list is not
    最近把线上数据库备份到本地数据库进行一些代码修改时候,发现代码连接本地数据库报错,线上数据库是正常的,后来查阅了一下是SELECT列表不在GROUPBY语句内且存在不函数依赖GROUPBY语句的非聚合字段,算是比较严谨的sql模式,如果需要解决的话需要修改一下my.ini配置页面,我先去自己安装......
  • 堆排序(Heap sort)
    堆排序堆排序是简单选择排序的改进,改进点为如何让减少在选择的过程中比较的次数。1.堆的定义    堆是具有以下性质的完全二叉树:每个结点的值都大于(小于)等于其孩子节点的值,称为大根堆(小根堆)。例:   由堆的定义得知堆顶元素一定为最大(大根堆)或者最小值(小根堆)。......
  • Java字符串逗号分隔转换List集合
    开发中常用String字符串接收多个用逗号或分号分隔的id,之后再将字符串处理成List<String>集合来方便使用数据。常用方式1.For循环添加Stringstr="123,456,789";List<String>listIds=newArrayList<>();String[]split=str.split(",");for(Strings:split){......