forked from shichao-an/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsolution.py
More file actions
34 lines (33 loc) · 1.03 KB
/
Copy pathsolution.py
File metadata and controls
34 lines (33 loc) · 1.03 KB
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
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a ListNode
def insertionSortList(self, head):
h = head # h is the temporary head node
# First node of h
if head is not None:
head = head.next
h.next = None
while head is not None:
next_node = head.next
# Insertion sort
current = h
prev = h
while current is not None and head.val > current.val:
prev = current
current = current.next
# head is smaller than the head node of h
# Insert head to the beginning of h
if prev == current:
head.next = h
h = head
# Insert head to the middle or end of h
else:
prev.next = head
head.next = current
head = next_node
return h