Recursive C++ Mergesort


  • 0
    T

    Splitting the list is the annoying part. Otherwise standard recursive merge of two sorted lists.

    ListNode *splitList(ListNode *node, int len)
    {
      if (node == NULL) return NULL;
      ListNode *prev = NULL;
      for (int i = 0; i < len; i++) {
        prev = node;
        node = node->next;
      }
      prev->next = NULL;
      return node;
    }
    
    ListNode *mergeList(ListNode *l1, ListNode *l2)
    {
      if (l1 == NULL) return l2;
      if (l2 == NULL) return l1;
      if (l1->val < l2->val) {
        auto next = l1->next;
        l1->next = mergeList(next, l2);
        return l1;
      } else {
        auto next = l2->next;
        l2->next = mergeList(next, l1);
        return l2;
      }
    }
    
    ListNode *sortList(ListNode *head, int len)
    {
      if (head == NULL) return NULL;
      if (len == 1) return head;
      int leftLen = len / 2;
      int rightLen = len - leftLen;
      auto l1 = sortList(splitList(head, rightLen), leftLen);
      auto l2 = sortList(head, rightLen);
      return mergeList(l1, l2);
    }
    
    

Log in to reply
 

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