:type head: ListNode :rtype: ListNode
(self, head)
| 6 | |
| 7 | class Solution(object): |
| 8 | def insertionSortList(self, head): |
| 9 | """ |
| 10 | :type head: ListNode |
| 11 | :rtype: ListNode |
| 12 | """ |
| 13 | # https://discuss.leetcode.com/topic/8570/an-easy-and-clear-way-to-sort-o-1-space |
| 14 | if head is None: |
| 15 | return None |
| 16 | helper = ListNode(-1000) |
| 17 | pre, curr = helper, head |
| 18 | while curr is not None: |
| 19 | next_step = curr.next |
| 20 | while pre.next and pre.next.val < curr.val: |
| 21 | pre = pre.next |
| 22 | curr.next = pre.next |
| 23 | pre.next = curr |
| 24 | pre = helper |
| 25 | curr = next_step |
| 26 | return helper.next |