`
betakoli
  • 浏览: 168449 次
社区版块
存档分类
最新评论

LeetCode Sort List

 
阅读更多

Sort List

sort a linked list in O(n log n) time using constant space complexity.

排序,时间复杂度为n(logn),

 

我们知道堆排序,归并排序即使在最坏的情况下时间复杂度为n(logn)。

 

这里使用链表的归并排序实现。

 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
       public ListNode sortList(ListNode head) {
    	if(head==null)
    		return null;
    	if(head.next==null)
    		return head;
    	ListNode p = head;
        ListNode q = head;
        while(q.next!=null&&q.next.next!=null)
        {
        	p=p.next;
        	q=q.next.next;
        }
        q=p.next;
        p.next=null;
        p=head;
        p=sortList(p);
        q=sortList(q);
        return merge(p,q);
    }
    
    public ListNode merge(ListNode p,ListNode q)
    {
        ListNode r = new ListNode(0);
        ListNode res = r;
        while(p!=null||q!=null)
        {
        	int a,b;
            if(p==null)
            	a = Integer.MAX_VALUE;
            else 
            	a=p.val;
            if(q==null)
            	b = Integer.MAX_VALUE;
            else 
            	b=q.val;
            if(a<=b)
            {
            	r.next=p;
            	p=p.next;
            }
            if(a>b)
            {
            	r.next=q;
            	q=q.next;
            }
        	r=r.next;
        }
        return res.next;
    }
}

 再来熟悉下排序的时间复杂度:



 

  • 大小: 18.8 KB
分享到:
评论

相关推荐

    python-leetcode题解之147-Insertion-Sort-List

    python python_leetcode题解之147_Insertion_Sort_List

    LeetCode最全代码

    * [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...

    LeetCode-Python代码.rar

    例如,在解决搜索和排序问题时,Python内置的`list`数据结构和相关的操作函数如`sort()`、`append()`等,能快速实现各种功能。 接着,我们来看数据结构。在LeetCode中,常见的数据结构包括数组、链表、栈、队列、树...

    javalruleetcode-LeetCode:LeetCode算法问题

    Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest ...

    Leetcode题目+解析+思路+答案.pdf

    - **Sort List**:对链表进行排序。 - **Rotate List**:将链表顺时针旋转指定次数。 - **Reorder List**:按照特定规则重新排列链表。 - **Partition List**:将链表按值分割成两个部分。 - **Add Two Numbers...

    Leetcode答案(c++版)

    **1.12 Insertion Sort List (147)** - **问题描述**:对链表进行插入排序。 - **解题思路**: - 创建一个虚拟头节点,用于记录排序后的链表起始位置。 - 依次将原链表中的节点插入到已排序部分的适当位置。 **...

    Python刷LeetCode汇总.zip

    Python的内置数据结构如list、dict、set、tuple等都能在这些题目中大显身手。理解它们的特性和操作方法是解决问题的关键。 2. **递归与回溯**:在算法中,递归和回溯经常用于解决复杂的问题,例如搜索、图遍历或...

    leetcode题目分类

    如数组(array)、链表(linked list)、字符串(string)、哈希表(hashtable)、栈(stack)、队列(queue)、二叉树(binary tree)、图(graph)、动态规划(DP)、数学问题(Math)、双指针技巧(Two Pointers...

    LeetCode解题包

    2. **C++标准库**:C++标准库提供了大量预先定义的函数和数据结构,如容器(vector、list、set、map)、迭代器、算法(排序、查找)等。在解题过程中,这些工具被广泛用于优化算法和提高代码效率。 3. **数据结构**...

    LeetCode_No80.rar_leetcode_leetcode c++代码

    - **STL库**:利用标准模板库(STL)中的容器(如vector、list、set)、算法(如sort、find)和迭代器来简化代码。 - **模板和泛型编程**:当需要编写可重用的代码时,可以使用模板来实现泛型功能。 - **面向对象...

    leetcode卡-LeetCode:我的LeetCode解决方案

    list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡[LeetCode 3. Longest Substring Without Repeating Characters], N/A 2017.06.15 打卡[LeetCode 407. Trapping Rain Water II], BFS/...

    cpp-Leetcode问题的完整解决方案每日更新

    STL(标准模板库)提供了丰富的数据结构和算法,如 vector、list、map、set、sort 等,极大地简化了编程工作;同时,C++ 的内存管理更加灵活,允许程序员直接操作指针,这对于理解和优化算法性能非常有帮助。 "cpp-...

    _leetcode-python.pdf

    - Sort Colors: 给定一个包含红色、白色和蓝色,一共n个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 - Combinations: 从n个不同元素中取出k个元素的组合。 - ...

    算法-leetcode-剑指offer上的题很多

    - **链表(Linked List)**: 由一系列节点组成的集合,每个节点包含数据部分和指向下一个节点的指针。 - **二叉树(Binary Tree)**: 一种树形数据结构,每个节点最多有两个子节点,通常用于实现快速查找和排序操作。 - ...

    cpp-LeetCode的解题代码和中文讲解

    5. **STL库**:标准模板库(STL)提供了大量现成的数据结构和算法,如容器(vector、list、set等)、算法(sort、find等)和迭代器,熟练运用STL可以简化代码并提高代码质量。 6. **异常处理**:在编写C++代码时,...

    leetcode中325题python-leetcode:leetcode

    leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动

    最大公共字符串leetcode-leetCode:leetcode

    最大公共字符串leetcode leetcode 数组 链表 二叉树 位操作 判断字符串的顺序排列 给定一个字符串数组,将字谜组合在一起。 例如,给定:["eat", "tea", "tan", "ate", "nat", "bat"], public class Solution { ...

    Leetcode101.zip

    - **排序**:快速排序、归并排序、堆排序等都是LeetCode中常遇到的排序算法,C++的`std::sort`函数能处理大部分排序需求。 - **搜索**:线性搜索、二分搜索、深度优先搜索(DFS)和广度优先搜索(BFS)是常用的...

    Leetcode部分试题解析

    7. **Sort List**:对链表进行排序。可以先将链表转换为数组,然后使用快速排序或归并排序,最后将排序后的数组转换回链表。 8. **Search in Rotated Sorted Array**:在旋转有序数组中查找目标值。理解旋转数组的...

Global site tag (gtag.js) - Google Analytics