1
// Please upvote if it helps
2
class Solution {
3
 public:
4
  ListNode *sortList(ListNode *head) {
5
    // If List Contain a Single or 0 Node
6
    if (head == NULL || head->next == NULL) return head;
7

8
    ListNode *temp = NULL;
9
    ListNode *slow = head;
10
    ListNode *fast = head;
11

12
    // 2 pointer appraoach / turtle-hare Algorithm (Finding the middle element)
13
    while (fast != NULL && fast->next != NULL) {
14
      temp = slow;
15
      slow = slow->next;       // slow increment by 1
16
      fast = fast->next->next; // fast incremented by 2
17
    }
18
    temp->next = NULL; // end of first left half
19

20
    ListNode *l1 = sortList(head); // left half recursive call
21
    ListNode *l2 = sortList(slow); // right half recursive call
22

23
    return mergelist(l1, l2); // mergelist Function call
24
  }
25

26
  // MergeSort Function O(n*logn)
27
  ListNode *mergelist(ListNode *l1, ListNode *l2) {
28
    ListNode *ptr = new ListNode(0);
29
    ListNode *curr = ptr;
30

31
    while (l1 != NULL && l2 != NULL) {
32
      if (l1->val <= l2->val) {
33
        curr->next = l1;
34
        l1 = l1->next;
35
      } else {
36
        curr->next = l2;
37
        l2 = l2->next;
38
      }
39

40
      curr = curr->next;
41
    }
42

43
    // for unqual length linked list
44

45
    if (l1 != NULL) {
46
      curr->next = l1;
47
      l1 = l1->next;
48
    }
49

50
    if (l2 != NULL) {
51
      curr->next = l2;
52
      l2 = l2->next;
53
    }
54

55
    return ptr->next;
56
  }
57
};