leetcode148--Sort List(链表排序)(要重视)

leetcode148--Sort List(链表排序)(要重视)

题目

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

Example 1:

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

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

这个是用归并排序来做的,这里其实牵涉到了好几个题,比如如何找到链表的中间节点,方法就是用两个指针,一个fast一次走两步,slow的一次走一步,当fast的走到头的时候slow所在的位置就是中间的节点.

然后还有如何对两个排好序的链表进行排序的问题,

写下来就是


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

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if (not head) or (not head.next):
            return head
        
        ## 然后就是一半的地方
        
        slow = head
        fast = head
        pre = head
        
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None
        
        return self.merge(self.sortList(head), self.sortList(slow))
        
        
    def merge(self, ls1, ls2):
        
        ls3 = ListNode(-1)
        ret = ls3
        
        # 用ret去不断的next最后返回ls3的next
        
        while ls1 and ls2:
            if ls1.val <= ls2.val:    # <和<=这里都是可以的.
                ret.next = ls1
                ls1 = ls1.next
            else:
                ret.next = ls2
                ls2 = ls2.next
                
            ret = ret.next
            
        ## 别忘了最后把没有用完的给接上去.
        if ls1:
            ret.next = ls1
        if ls2:
            ret.next = ls2
            
        return ls3.next
        

后面的merge函数就是归并两个有序的链表的过程,这个归并和数组不太一样的地方还有一点,即如果要把链表分成两个部分的话,需要知道其中间的节点,不光如此还要得到前半段的链表和后半段的链表。 所以用了一个pre来记录当前的位置,因为前半段节点结束的时候,后面没有了,所以pre.next=None, 然后前半段节点是head 后半段节点是从slow开始的. 这个是用递归来写的,程序递归到最后的时候应该只有两上元素了,所以它们 会直接合并成一个,然后再不断地进行这种合并, 那么最终得到的就是排好序的了.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦