Leetcode之Sort List-白红宇

Leetcode之Sort List

阅读量：2342 次

发布时间：2019-05-10

本文共 2385 字，大约阅读时间需要 7 分钟。

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

to see which companies asked this question

解题报告：就是对一个链表进行归并排序。

主要考察3个知识点，

知识点1：归并排序的整体思想

知识点2：找到一个链表的中间节点的方法

知识点3：合并两个已排好序的链表为一个新的有序链表

归并排序的基本思想是：找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个以排好序的链表进行Merge

python代码：

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def sortList(self, head):        """        :type head: ListNode        :rtype: ListNode        """        if head == None or head.next == None:            return head;                medium = self.getMiddle(head)        next = medium.next        medium.next = None                return self.mergeList(self.sortList(head), self.sortList(next))            def getMiddle(self, head):        slow = head        fast = head                while fast.next != None and fast.next.next != None:            slow = slow.next            fast = fast.next.next        return slow            def mergeList(self, former, latter):        dummy_head = ListNode(-1)        cur = dummy_head                while former != None and latter != None:            if former.val <= latter.val:                cur.next = former                former = former.next            else:                cur.next = latter                latter = latter.next            cur = cur.next                if former != None:            cur.next = former        if latter  != None:            cur.next = latter                return dummy_head.next

Java代码：

 public class Solution {  
      //use the fast and slow pointer to get the middle of a ListNode  
      ListNode getMiddleOfList(ListNode head) {  
         ListNode slow = head;  
         ListNode fast = head;  
         while(fast.next!=null&&fast.next.next!=null) {  
             slow = slow.next;  
             fast = fast.next.next;  
         }  
         return slow;  
     }  
       
     public ListNode sortList(ListNode head) {  
         if(head==null||head.next==null) {  
             return head;  
         }  
         ListNode middle = getMiddleOfList(head);  
         ListNode next   = middle.next;  
             middle.next = null;  
         return mergeList(sortList(head), sortList(next));  
     }  
       
     //merge the two sorted list  
     ListNode mergeList(ListNode a, ListNode b) {  
         ListNode dummyHead = new ListNode(-1);  
         ListNode curr = dummyHead;  
         while(a!=null&&b!=null) {  
             if(a.val<=b.val) {  
                 curr.next=a;a=a.next;  
             } else {  
                 curr.next=b;b=b.next;  
             }  
             curr  = curr.next;  
         }  
         curr.next = a!=null?a:b;  
         return dummyHead.next;  
     }  
 }  