Merge Sort Solution (using fast slow pointer to find the middle node)


  • 0
    A

    /**

    • 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) {
      return mergeSort(head);
      }
      private:
      ListNode* mergeSort(ListNode* head)
      {
      if(head == NULL|| head->next == NULL) return head;
      ListNode* fast = head;
      ListNode* slow = head;
      //find the middle node
      while(fast->next != NULL && fast->next->next != NULL)
      {
      slow = slow->next;
      fast = fast->next->next;
      }
      ListNode* mid = slow->next;
      slow->next = NULL;
      ListNode* op1 = mergeSort(head);
      ListNode* op2 = mergeSort(mid);
      //merge process
      ListNode* sortedList = new ListNode(0);
      ListNode* op3 = sortedList;
      while(op1 != NULL || op2 != NULL)
      {
      if(op2 == NULL || (op1 != NULL && op1->val < op2->val))
      {
      op3->next = op1;
      op3 = op3->next;
      op1 = op1->next;
      }
      else
      {
      op3->next = op2;
      op3 = op3->next;
      op2 = op2->next;
      }
      }
      op3 = sortedList->next;
      delete sortedList;
      return op3;
      }

    };


Log in to reply
 

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