Sort a linked list in O(n log n) time using constant space complexity.
题目要求用 O(n log n)的时间复杂度和常数的空间复杂度来进行链表排序。
O(nlogn)的排序算法有堆排,快排,归并排序等,一开始我准备采用快排,后来发现每次需要交换元素的时候的十分痛苦。而实用归并排序,其实本身就是调用
Merge Two Sorted Lists。所以还是使用归并来得简单一些。进行链表排序和数组排序的不同点在于需要维护一个前序结点,维持链表的连续性。另外这里不能使用index来直接获得左右子链表,需要做一次遍历来割取左右子链表。一个办法是使用slow和fast两个指针,fast每次走两步,slow每次走一步,fast到达尾部时,slow就到达了链表中部。这样实现的代码如下:
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next :
return head
dummy = ListNode(-1)
dummy.next = head #防止头结点需要换位,先建立一个辅助的先序结点
slow = fast = dummy #一慢一快两个指针
#分割左右两个子链表
while fast and fast.next:
slow = slow.next
fast = fast.next.next
tmp = slow.next #注意为了合并左右子链表,需要将第一个子链表尾结点的next置为None。
slow.next = None
slow = tmp
left = self.sortList(head) #递归排序左子链表
right = self.sortList(slow) #递归排序右子链表
cur = dummy
#merge操作
while left and right:
if left.val < right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
cur.next = left if left else right
return dummy.next
上述的解法需要递归的,空间复杂度为O(nlogn),所以其实不符合题目要求的常数空间复杂度的要求。时间上每次进行左右分割的时间和merge的时间复杂度都是O(n)。总体的时间复杂度还是O(nlogn)。
对上述的代码去递归,采用迭代处理。思路时先进行相邻2个结点的排序,之后进行4个,然后8个,这种自底向上的思路在CUDA高性能计算上也有应用。思路很熟悉。主要时维护一个step,开始为1,然后为2,之后是4,示意如下:
Round #1 block_size = 1
(a1, a2), (a3, a4), (a5, a6), (a7, a8)
Compare a1 with a2, a3 with a4 ...
Round #2 block_size = 2
(a1, a2, a3, a4), (a5, a6, a7, a8)
merge two sorted arrays (a1, a2) and (a3, a4), then merge tow sorted arrays(a5, a6) and (a7, a8)
Round #3 block_size = 4
(a1, a2, a3, a4, a5, a6, a7, a8)
实现的代码如下:
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
dummy = ListNode(-1)
dummy.next = head
length = 0
cur = head
while(cur): #get the length
length += 1
cur = cur.next
step = 1
while step < length: #the main part of sorting, from short length to long length
cur = dummy.next
tail = dummy
while cur:
l = cur
r = self.split(l, step)
cur = self.split(r, step)
tail = self.merge(l, r, tail)
step <<= 1
return dummy.next
#分割要排序的块,返回该块尾结点的后一个结点。
def split(self,start, step):
if not start:
return None
for i in xrange(step-1):
if start:
start = start.next
else:
return None
if not start:
return None
end = start.next
start.next = None
return end
#合并两个链表,注意要返回排序后的链表的尾结点,方便后序的连接
def merge(self,l, r, head):
if not r:
head.next = l
cur = head
while l and r:
if l.val < r.val:
cur.next = l
l = l.next
else:
cur.next = r
r = r.next
cur = cur.next
cur.next = l if l else r
while cur.next: #找寻尾结点
cur = cur.next
return cur
上述思路不难,但是和所有的链表题一样,需要考虑找这个结点,还是前序还是后序,如何建立连接,如何防止越界。考虑的corner case比较多。