问题描述:
Sort a linked list using insertion sort.
原问题链接:https://leetcode.com/problems/sort-list/
问题分析
有时候,往往是一些看似简单的问题描述 ,其解决方法越麻烦。这里问题描述确实简单,对于一个链表来说,我们需要寻找一种时间复杂度为O(NlogN)的排序法。对于数组来说,要找到这种时间复杂度的方法有好几种,比如说归并排序,快速排序,堆排序等。这些都是建立在基于数组的索引访问很方便的基础之上的。
可是对于链表来说,这又是一个要命的问题。它最方便的访问法就是只能从头往后一个个的访问下去。如果要访问到其中的某个索引位置则相对慢很多。看来我们需要从上述的几种方法中找一种对于索引访问比较少,这样使得方法的性能没有太大影响的才行。
我们可以考虑归并排序,它是递归的将一组元素划分成两个部分,一直到无法继续划分位置。然后在递归返回的时候将相邻的两个部分给合并起来。在这里,我们可以将链表首先划分成两个部分。这里可以采用前面快慢指针的手法。这样就得到了两个链表。
然后我们再针对两个链表进行合并。而合并链表的手法在之前的一些方法里也有过讨论,我们就是建立一个临时节点,然后将它们两个链表按照大小往里面加。同时每次也移动新链表里元素的节点。
这样,把这两个点解决之后,就好办了。我们可以得到如下的详细代码实现:
/** * 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 || head.next == null) return head; ListNode fast = head, slow = head, pre = null; while(fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; ListNode first = sortList(head); ListNode second = sortList(slow); return merge(first, second); } private ListNode merge(ListNode first, ListNode second) { ListNode dummy = new ListNode(0); ListNode pre = dummy; while(first != null && second != null) { if(first.val < second.val) { pre.next = first; first = first.next; } else { pre.next = second; second = second.next; } pre = pre.next; } if(first != null) pre.next = first; if(second != null) pre.next = second; return dummy.next; } }
相关推荐
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 ...
list:链表相关题目 stack:栈相关题目 queue:队列相关题目 string:字符串处理相关题目 tree:树相关题目 divide Conquer: 分治法相关题目 dynamic Programming:动态规划 graph:图论 greedy:贪心算法 recursion:...
leetcode 答案 leetcode Day 1 两数之和: 1。 考虑两层嵌套循环 2。...用dictionary以及 ...List[int], ...List[int]: ...List[int], ...List[int]: ...temp.sort() i=0 j=len(nums)-1 while i<j>target: j=j-1 elif (temp
最大公共字符串leetcode leetcode 数组 链表 二叉树 位操作 判断字符串的顺序排列 给定一个字符串数组,将字谜组合在一起。 例如,给定:["eat", "tea", "tan", "ate", "nat", "bat"], public class Solution { ...
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/...
Sort & Search # Name Difficulty Solution index 1 直接插入 easy python :heart_suit: 2 简单选择排序 easy python :heart_suit: 3 冒泡排序 easy python :heart_suit: 4 希尔 easy python :heart_suit: 5 快排...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
frequecy_sort.py: height_checker.py: Jewels_and_stones.py: last_stone_weight.py: Linked_list_cycle.py: long_pressed_name.py: max_69_number.py: max_array_sum_after_negations.py: max_depth_n_ary...
list unordered_map<> 88 有序数组 合并两个vector STL vector array 26 就地删除重复元素 直接用STL sort() unique() erase()做的 122 买卖股票的最佳时机 利润最大化就是每次波谷买入波峰卖出 189 旋转数组 ...
java lru leetcode leetcode Description My leetcode solutions. Statistics language num C++ 308 Python3 46 JavaScript 4 Java 2 SQL ...Sort ...Sort ...Sort ...Topological-Sort-拓扑排序 ...List 双向链表
leetcode下载 Leetcode 刷题记录 01. Two Sum 暴力破解时间复杂度高,使用hash表降低时间复杂度 02. Add Two Numbers 由于链表是逆置的,所以直接顺序遍历两个链表,按照加法器规则依次相加各节点,并进位 最后一组...
LeetCode 解决方案。 不。 标题 笔记 标签 1 Array 2 Linked List 3 Hash Table String 4 Array Divide and Conquer Binary Search Divide and Conquer 7 Math 24 Linked List 27 Array 33 Array Binary Search 79 ...
leetcode 分类 ReadMe 纯粹记录一下自己leetCode做题记录及部分思路笔记,不充当指导性repo 加油!...sort 循环排序 list 链表 ... 这些tag分类都可以在一些平台上找到,VSCode中也有响应的分类tag
List ) 栈 ( Stack ) 树 ( Tree ) 二叉搜索树 ( BST ) 字典树(前缀树) ( Trie ) 哈希表 ( Hash Table ) 堆 ( Heap ) 图 ( Graph ) 二分查找 ( Binary Search ) 位运算 ( Bit Manipulation ) 分治算法 ( Divide And...
list.sort( key = lambda x: x[1] ) 图 = collections.defaultdict(list) heapq.heapify (列表) a = heapq.pop(队列) heapq.push(队列,ele) dq = collections.deque(list) append, appendleft, clear, copy...
leetcode 2 sum c LeetCode LeetCode 个人题解, 解法基于C++ Content Title Difficulty Solution ...sort ...List 20. Easy stack 21. Easy merge sort 22. Medium recursion、dfs 23. Hard heap sort
Collections.sort(List,Comparator) 对列表进行排序 反向链表(给定链表反向部分的长度) ListNode start = pre.next; ListNode then = start.next; //key part of reversing given length linkedlist for(int i =...