LeetCode #148 2018-07-28

148. Sort List

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

Example1:
Input: 4->2->1->3
Output: 1->2->3->4
Example2:
Input: 4->2->1->3
Output: 1->2->3->4

https://leetcode.com/problems/sort-list/description/

这道题可以用Merge Two Sorted Lists作为合并的子操作，然后用归并排序的递归进行分割合并就可以了。我们需要做的就是每次找到中点，然后对于左右进行递归，最后用Merge Two Sorted Lists把他们合并起来。不过用归并排序有个问题就是这里如果把栈空间算上的话还是需要O(logn)的空间的。

排序是面试中比较基础的一个主题，所以对于各种常见的排序算法大家还是要熟悉，不了解的朋友可以参见排序算法 - Wiki。特别是算法的原理，很多题目虽然没有直接考察排序的实现，但是用到了其中的思想，比如非常经典的topK问题就用到了快速排序的原理，关于这个问题在Median of Two Sorted Arrays中有提到。
代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        walker = head
        runner = head
        while(runner.next and runner.next.next):
            walker = walker.next
            runner = runner.next.next
        head1 = head
        head2 = walker.next
        walker.next = None
        head1 = self.sortList(head1)
        head2 = self.sortList(head2)
        return self.mergeTwoLists(head1, head2)
        
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = l1
        pre = dummy
        while(l1 and l2):
            if l1.val <= l2.val:
                l1 = l1.next
            else:
                next = l2.next
                l2.next = pre.next
                pre.next = l2
                l2 = next
            pre = pre.next
        if l2:
            pre.next = l2
        return dummy.next

感悟:

1. 循环条件要灵活多变，根据题目要求来设定。该题需要取walker.next作为head2，要提前1步结束，否则不能均分链表为2段，所以循环条件为runner.next and runner.next.next。
2. 找到中点后需将walker.next指针置空，walker.next = None即切断原链表为2个子链表。
3. 用merge作为subroutine，divide之后conquer，最后完成merge sort。
   核心代码代码如下：

        head1 = head
        head2 = walker.next
        walker.next = None
        head1 = self.sortList(head1)
        head2 = self.sortList(head2)
        return self.mergeTwoLists(head1, head2)