【LeetCode】147. Insertion Sort List 解题报告(Python)
【LeetCode】147. Insertion Sort List 解题报告(Python)
标签(空格分隔): LeetCode
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.me/
题目地址:https://leetcode.com/problems/insertion-sort-list/description/
题目描述:
Sort a linked list using insertion sort.
A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list
Algorithm of Insertion Sort:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
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.
It repeats until no input elements remain.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
题目大意
使用插入排序,对链表进行排序。
解题方法
这个算链表里边的难题了,其实就是模拟题目中图的过程,稍微有点复杂的就是指针的操作。参考了:链表插入排序里的做法,链表操作多用几个指针就方便很多了。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next: return head
root = TreeNode(0)
root.next = head
while head.next:
if head.val <= head.next.val:
head = head.next
else:
temp = head.next
q = root
head.next = head.next.next
while q.next and q.next.val < temp.val:
q = q.next
temp.next = q.next
q.next = temp
return root.next
日期
2018 年 6 月 23 日 ———— 美好的周末要从刷题开始
最新文章
- 【hihoCoder】1288 : Font Size
- Elasticsearch——使用_cat查看Elasticsearch状态
- jQuery 调用jsonp实现与原理
- 1.7.7 Spell Checking -拼写检查
- 单片机C语言下LCD多级菜单的一种实现方法
- office文件密码破解方法及软件
- python之--条件判断和循环
- Java内部类的总结
- JAVA通过Gearman实现MySQL到Redis的数据同步(异步复制)
- jQuery学习笔记一
- Windows Server 2016-命令行批量导出AD用户列表信息
- 急速JavaScript全栈教程
- form的重置reset
- 第7月第25天 xcode bundle calayer动画
- Spring Cloud Config 自动刷新所有节点 架构改造
- 线程函数对比 win/linux
- Android之旅十四 android中的xml文件解析
- wpa安装方法
- unity 小地图的制作
- 利用socket.io+nodejs打造简单聊天室