Leetcode[147] Insertion Sort List
11 Nov 2015###Task1 Sort a linked list using insertion sort.
###Python ####Easy
# 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:
return None
imin = (-1 << 63)
dummy = ListNode(imin)
dummy.next = head
cur = dummy
while cur.next:
if cur.val < cur.next.val:
cur = cur.next
else:
insert = cur.next
cur.next = insert.next
start = dummy
while start.val < insert.val:
prev = start
start = start.next
prev.next = insert
insert.next = start
return dummy.next
####TLE
# 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:
return None
dummy = ListNode(head.val)
itr = head.next
while itr:
inner = dummy
post = itr.next
if itr.val <= dummy.val:
oldHead = dummy
dummy = itr
dummy.next = oldHead
itr = post
continue
while inner.next:
if inner.val < itr.val and inner.next.val >= itr.val:
oldNext = inner.next
inner.next = itr
itr.next = oldNext
break
inner = inner.next
if not inner.next and itr.val > inner.val:
inner.next = itr
itr.next = None
itr = post
return dummy
###Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
// class ListNode {
// int val;
// ListNode next;
// ListNode(int x) {
// val = x;
// }
// }
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(head.val);
ListNode pointer = head.next;
while (pointer != null) {
ListNode innerPointer = dummy;
ListNode next = pointer.next;
//head
if (pointer.val <= dummy.val) {
ListNode oldHead = dummy;
dummy = pointer;
dummy.next = oldHead;
pointer = next;
continue;
}
while (innerPointer.next != null) {
//middle
if (pointer.val > innerPointer.val && pointer.val <= innerPointer.next.val) {
ListNode oldNext = innerPointer.next;
innerPointer.next = pointer;
pointer.next = oldNext;
break;
}
innerPointer = innerPointer.next;
}
//tail
if (innerPointer.next == null && pointer.val > innerPointer.val) {
innerPointer.next = pointer;
pointer.next = null;
}
pointer = next;
}
return dummy;
}
}
###Points
- O(n2) in average
- The reason for TLE: if the list is already sorted, the first method is better and achieve O(n) time.