链接列表的归并排序
我在使用归并排序对链表进行排序时遇到了一些麻烦。我发现问题出在我的分区方法上。
每当我进行分区并请求前半部分时，另一半却和之前的部分完全一样。但是如果我不请求前半部分，后半部分就能正确返回。下面是我的代码：
class ListNode:
def __init__(self, x, next = None):
self.val = x
self.next = next
def print_list(root):
while root:
print root.val,
root = root.next
print ''
def partition(root, is_first_half):
print_list(root)
if not root.next:
return root
slow_pointer, fast_pointer = root, root.next
while fast_pointer and fast_pointer.next != None:
fast_pointer = fast_pointer.next.next
slow_pointer = slow_pointer.next
if not is_first_half:
return slow_pointer
first_half, first_half_head, first_half_pointer = None, None, root
while first_half_pointer and first_half_pointer != slow_pointer:
if not first_half_head:
first_half = first_half_pointer
first_half_head = first_half
else:
first_half.next = first_half_pointer
first_half = first_half_pointer
first_half.next = None
first_half_pointer = first_half_pointer.next
return first_half_head
def merge(list1, list2):
new_list_head, new_list = None, None
if not list1:
return list2
if not list2:
return list1
while list1 and list2:
if list1.val < list2.val:
if not new_list_head:
new_list = list1
new_list_head = new_list
else:
new_list.next = list1
new_list = list1
new_list.next = None
list1 = list1.next
else:
if not new_list_head:
new_list = list2
new_list_head = new_list
else:
new_list.next = list2
new_list = list2
new_list.next = None
list2 = list2.next
if not list1:
while list2:
new_list.next = list2
new_list = list2
new_list.next = None
list2 = list2.next
return new_list_head
while list1:
new_list.next = list1
new_list = list1
new_list.next = None
list1 = list1.next
return new_list_head
def mergesort(root):
if not root.next:
return root
list1 = mergesort(partition(root, True))
list2 = mergesort(partition(root, False))
return merge(list1, list2)
if __name__ == '__main__':
a = ListNode(2, ListNode(4, ListNode(3, ListNode(1, ListNode(7)))))
print_list(a)
a = mergesort(a)
print_list(a)
3 个回答
首先，在你代码的前半部分，对于第二个元素，你调用了
first_half = first_half_pointer
first_half.next = None
然后
first_half_pointer = first_half_pointer.next
所以 first_half_pointer 变成了 None，循环结束了，这样第一半部分的元素最多只有两个。
其次，更重要的是，你通过这一行代码打断了原始列表的连接：
first_half.next = None
所以在执行 partition(root, True) 之后，列表的后半部分就丢失了。
你想要的分区是破坏性的还是非破坏性的？也就是说，运行分区后，原来的列表还会保留所有的值吗？你可以选择任何一种方式来分区。
破坏性分区可能会稍微快一点，因为它只需要断开一个节点的连接（不过找到那个节点的时间是O(N)）。如果你想要非破坏性地获取列表的前半部分，你需要复制它（为每个值创建新的节点）。这同样是O(N)，但可能因为内存分配的原因，实际的时间会更长。
这里有一个简单的破坏性分区示例。它使用了不同的初始值，所以我们可以直接在slow_pointer之后进行分割，而不是在之前（那样会更复杂）。而且，分区时一次只获取一个半部分其实没有太大意义，因为如果你请求了前半部分，后半部分就无法再访问了，所以我们总是返回两个半部分。
def partition(root):
fast_pointer = slow_pointer = ListNode(None, root) # new node "before the root"
while fast_pointer and fast_pointer.next:
fast_pointer = fast_pointer.next.next
slow_pointer = slow_pointer.next
mid = slow_pointer.next
slow_pointer.next = None # break one link in the list
return root, mid # return both halves of the list
这里有一个非破坏性的版本。列表的后半部分仍然引用原来的节点，但返回的前半部分是新节点的复制。
def partition_non_destructive(root):
root = fast_pointer = slow_pointer = ListNode(None, root) # root anchors the copy
while fast_pointer and fast_pointer.next:
fast_pointer = fast_pointer.next.next
slow_pointer.next = ListNode(slow_pointer.next.value, # copy the next node
slow_pointer.next.next)
slow_pointer = slow_pointer.next # slow_pointer is always the latest copied node
mid = slow_pointer.next
slow_pointer.next = None # unlink copied half from the rest
return root.next, mid # return both halves of the list
这两个函数都能正确处理任何长度的列表，包括长度为一（ListNode("foo")）和长度为零（None）。对于奇数长度的列表，返回的前半部分总是会比后半部分大。
你的 merge 方法似乎有个问题，它会把列表中的一些元素丢掉。想想下面这行代码会发生什么：
new_list.next = None
这样做实际上是把剩下的列表给丢掉了。看起来每次合并时，你只会保留整体中最小的元素，以及每个列表中的最小元素，总共只保留三个元素。试试下面的 main 方法，看看我说的是什么意思：
if __name__ == '__main__':
a = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
b = ListNode(6, ListNode(7, ListNode(8, ListNode(9, ListNode(10)))))
print_list(a)
print_list(b)
#a = mergesort(a)
c = merge(a, b)
print_list(c)
print_list(a)
print_list(b)