# Leetcode: Sort List Similar Problems:

Sort a linked list in O(n log n) time using constant space complexity.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/sort-list
## Basic Ideas: Merge sort. Recursive
##       1. Divide the list into two half
##       2. Merge sort these two
##       3. Combine two sorted list
##          5  -> 6 -> 2 -> 7 -> 4
## Complexity: Time O(n*log(n)), Space O(1)

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
length = 0
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next

prev.next = None

# merge two sorted list
dummyNode = ListNode(None)
while p1 and p2:
if p1.val <= p2.val:
# append p1 to the new list
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next

if p1 is None:
p1 = p2
p.next = p1
return dummyNode.next
```

Share It, If You Like It.