[leetcode题解]148.sort list

leetcode第148题,sort list,题目给定一个单链表,要求用o(nlogn)的时间复杂度对链表进行排序,其实对于单链表的排序可以使用快排,也可以使用归并排序,对于已排序链表的合并由于比较简单,所以这里就使用归并排序实现一下。
设计了一个找链表中间节点的方法halfList,找到中间节点后将链表一分为二,左右各进行归并排序就好了,最后一个合并两个已排序链表的操作就可以了。
下面使用c++和python两种语言实现了一下

c++代码:

class Solution {
public:
    ListNode* sortList(ListNode* head) 
    {
        if (head == NULL || head->next == NULL)return head;
        
        ListNode *pre = new ListNode(-1);
        ListNode *tail = pre;
        
        ListNode *half = halfNode(head);
        
        ListNode *le = head, *ri = half->next;
        half->next = NULL;
        
        le = sortList(le);
        ri = sortList(ri);
        
        ListNode *p = le, *q = ri;
        while(p != NULL && q != NULL)
        {
            if (p->val < q->val)
            {
                tail->next = p;
                tail = tail->next;
                p = p->next;
            }
            else
            {
                tail->next = q;
                tail = tail->next;
                q = q->next;
            }
        }
        
        if (p != NULL)tail->next = p;
        else tail->next = q;
        //else tail->next = NULL;
        return pre->next;
    }
    
private:
    ListNode *halfNode(ListNode *head)
    {
        if (head == NULL || head->next == NULL)return head;
        ListNode *slow = head, *fast = head->next->next;
        
        while(fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

python代码:

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head
        
        half = self.halfList(head)
        li, ri = head, half.next
        half.next = None
        
        li = self.sortList(li)
        ri = self.sortList(ri)
        
        pre = ListNode(-1)
        tail = pre
        while li != None and ri != None:
            if li.val < ri.val:
                tail.next = li
                li = li.next
            else:
                tail.next = ri
                ri = ri.next
        
            tail = tail.next
        if li != None:
            tail.next = li
        else:
            tail.next = ri
        return pre.next
        
    def halfList(self, head):
        if head == None or head.next == None:
            return head
        fast = head
        slow = head
        while fast.next != None and fast.next.next != None:
            slow, fast = slow.next, fast.next.next
        return slow

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]148.sort list

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/65.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注