-
Notifications
You must be signed in to change notification settings - Fork 0
/
InsertionSortLL.py
34 lines (31 loc) · 942 Bytes
/
InsertionSortLL.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Problem: https://leetcode.com/problems/insertion-sort-list/discuss/
# 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
dummy = ListNode(0)
dummy.next = head
cur = head.next
prev = head
curr = dummy
while (cur):
if cur.val < prev.val:
while (curr.next.val < cur.val):
curr = curr.next
prev.next = cur.next
cur.next = curr.next
curr.next = cur
curr = dummy # reset curr
else:
prev = cur
cur = prev.next
return dummy.next