cPP, merge , O(nlogn)timecomplexity ,O(1)spacecomplexity


  • 0
    F

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      class Solution {
      public:
      ListNode
      sortList(ListNode* head) {
      if(head == NULL || head->next == NULL)
      {
      return head;
      }

       ListNode* slow;
       ListNode* headTwo;
       
       slow = getMid(head);
       
       headTwo = slow->next;
       slow->next = NULL;
       
       ListNode* p = sortList(head);
       ListNode* q = sortList(headTwo);
       
       return merge(p,q);
      

      }

      ListNode* getMid(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;
      

      }

      ListNode* merge(ListNode* p,ListNode* q)
      {
      ListNode* lc;
      ListNode* pc;

       if(p->val < q->val)
       {
           lc = pc = p;
           p = p->next;
       }
       else
       {
           lc = pc = q;
           q = q->next;
       }
       
       while(p != NULL && q != NULL)
       {
           if(p->val < q->val)
           {
               pc->next = p;
               p = p->next;
               pc = pc->next;
           }
           else
           {
               pc->next = q;
               q = q->next;
               pc = pc->next;
           }
       }
       
       if(p != NULL)
       {
           pc->next = p;
       }
       if(q != NULL)
       {
           pc->next = q;
       }
       
       return lc;
      

      }
      };


Log in to reply
 

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