链表插入排序

题意

用插入排序对链表排序

样例

给予 1->3->2->0->null, 返回 0->1->2->3->null

思路

将接受到的链表当做未排序链表,再创建一个链表存放已排序链表,并创建一个已排序链表的指针。

依次将未排序链表的元素与已排序链表中的每一个元素进行比较(也就是先用未排序链表的第一个与已排序链表的每一个进行比较,然后用未排序链表的第二个,第三个….依次进行比较,直到最后一个元素)

由于题意是升序排序,所以只要未排序链表中的元素大于已排序链表中的元素,那么就将未排序链表的这个元素放到第一个比它大的已排序链表的后面。

要注意的是,将未排序链表的元素放到已排序链表时,不要覆盖掉原数据(先挪动其他数据再进行插入操作)。

代码实现

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: The head of linked list.
     */
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        while (head != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < head.val) {
                node = node.next;
            }
            ListNode temp = head.next;
            head.next = node.next;
            node.next = head;
            head = temp;
        }
        return dummy.next;
    }
}

原题地址

LintCode:链表插入排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

求两个链表的交点

已知链表A的头节点指针headA,链表B的头节点指针headB,两个链表相交,求两链表交点对应的节点。 [](LeetCode 160)

652
来自专栏desperate633

LeetCode 2. Add Two Numbers题目分析代码

You are given two non-empty linked lists representing two non-negative integers....

893
来自专栏编舟记

Monad

什么是函数(Function)? 函数表达的映射关系在类型上体现在特定类型(proper type)之间的映射。

825
来自专栏诸葛青云的专栏

C语言中你必须知道的几大排序算法

在实际使用数组的过程中,数组不仅可以存储多个同类型的数据,而且要求这些数据按照某种特征进行排序。例如,学生的成绩,需要按照从高到低的顺序排列,这就需要使用排序算...

630
来自专栏HappenLee的技术杂谈

C++雾中风景7:闭包

闭包(closure)是函数式编程的重要的语法结构。 闭包的概念其实很简单,一言以蔽之:闭包是带有上下文的函数。说白了,就是有状态的函数。也就是说一个局部变量...

1152
来自专栏Jack-Cui

67.Add Binary(String-Easy)

Given two binary strings, return their sum (also a binary string). For example, ...

1796
来自专栏老马说编程

(26) 剖析包装类 (上) / 计算机程序的思维逻辑

包装类 Java有八种基本类型,每种基本类型都有一个对应的包装类。 包装类是什么呢?它是一个类,内部有一个实例变量,保存对应的基本类型的值,这个类一般还有一些...

22810
来自专栏黑泽君的专栏

java基础学习_面向对象(下)02_day09总结

============================================================================= ==...

852
来自专栏web前端教室

常用技巧之JS判断数组中某元素出现次数

现在前端开发经常需要从api中获取返回的数组, 也许是array,也许是json, 不管是什么,都需要对返回的数据进行再处理, 其中一个重要且经常用到的操作, ...

3948
来自专栏韦弦的偶尔分享

Swift 删除链表中的节点 - LeetCode

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

1593

扫码关注云+社区

领取腾讯云代金券