Non recursive merge sort solution in C++,constant space complexity,python also AC


  • 1
    M

    C++ version:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    private:
        void myMerge(ListNode *head, ListNode *p, ListNode *q)
        {
            while (p && q)
            {
                if (p->val < q->val)
                {
                    head->next = p;
                    p = p->next;
                    head = head->next;
                }
                else
                {
                    head->next = q;
                    q = q->next;
                    head = head->next;
                }
            }
            if (p) head->next = p;
            if (q) head->next = q;
        }
        
    public:
        ListNode *sortList(ListNode *head) {
            if (!head) return NULL;
            int n, i, j, k;
            ListNode *dummy = new ListNode(0);
            dummy->next = head;
            ListNode *p = head;
            ListNode *q = head;
            ListNode *pt = dummy;
            ListNode *qt = dummy;
            ListNode *pdummy = dummy;
            ListNode *qdummy = dummy;
            for (n = 1; p->next; n++)
                p = p->next;
            for (k = 1; k < n; k <<= 1)
            {
                pdummy = dummy;
                qdummy = dummy->next;
                while (qdummy)
                {
                    p = qdummy;
                    pt = p;
                    for (i = 0; i < k; i++)
                    {
                        qt = pt;
                        pt = pt->next;
                        if (pt == NULL)
                            break;
                    }
                    if (pt == NULL)
                    {
                        pdummy->next = qdummy;
                        break;
                    }
                    qt->next = NULL;
                    q = pt;
                    for (i = 0; i < k; i++)
                    {
                        qt = pt;
                        pt = pt->next;
                        if (pt == NULL)
                            break;
                    }
                    qdummy = pt;
                    qt->next = NULL;
                    
                    myMerge(pdummy, p, q);
                    if (qdummy)
                    {
                        for (i = 0; i < 2*k; i++)
                            pdummy = pdummy->next;
                    }
                }
            }
            return dummy->next;
        }
    };
    

    ================================================================

    python version:

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param head, a ListNode
        # @return a ListNode
        def myMerge(self, head, p, q):
            while p and q:
                if p.val < q.val:
                    head.next = p;
                    p = p.next;
                    head = head.next;
                else:
                    head.next = q;
                    q = q.next;
                    head = head.next;
            if p:
                head.next = p;
            if q:
                head.next = q;
        
        def sortList(self, head):
            if not head:
                return None
            dummy = ListNode(0)
            dummy.next = head
            p = head
            q = head
            pt = dummy
            qt = dummy
            pdummy = dummy
            qdummy = dummy
            n = 1
            while p.next:
                n += 1
                p = p.next
            k = 1
            while k < n:
                pdummy = dummy
                qdummy = dummy.next
                while qdummy:
                    p = qdummy
                    pt = p
                    for i in range(k):
                        qt = pt
                        pt = pt.next
                        if pt == None:
                            break
                    if not pt:
                        pdummy.next = qdummy
                        break
                    qt.next = None
                    q = pt
                    for i in range(k):
                        qt = pt
                        pt = pt.next
                        if not pt:
                            break
                    qdummy = pt
                    qt.next = None
                    
                    self.myMerge(pdummy, p, q)
                    if qdummy:
                        for i in range(2*k):
                            pdummy = pdummy.next
                k <<= 1
    
            return dummy.next

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.