Merge Sort a Linked List

 /**  
 *     Merge Sort a Linked List  
 *     Anwar Mamat  
 *     anwarmamat@gmail.com  
 *  
 */  
 #include <iostream>  
 using namespace std;  
 /*  
 *     Single Linked List Node  
 */  
 template <typename T>  
 class Node  
 {  
 public:  
      T data;  
      Node* next;  
      Node(const T& d):data(d),next(NULL){};  
      ~Node(){};  
 };  
 /*  
 *     Push an item into the linked list. The item is added to the head;  
 */  
 template<typename T>  
 void pushToLinkedList(Node<T>** head, const T& item)  
 {  
      Node<T>* t = new Node<T>(item);  
      if(*head == NULL){  
           *head = t;  
      }  
      else{  
           t->next = *head;  
           *head = t;  
      }  
 }  
 /*  
 *     Print the linked list  
 */  
 template<typename T>  
 void printLinkedList(Node<T> *head)  
 {  
      Node<T> *t = head;  
      while(t != NULL){  
           cout << t->data << ", ";  
           t = t->next;  
      }  
      cout << endl;  
 }  
 /*  
 *     delete the linked list  
 */  
 template<typename T>  
 void deleteLinkedList(Node<T> *head)  
 {  
      Node<T> *t = NULL;  
      while(head != NULL)  
      {  
           t = head->next;  
           delete head;  
           head = t;  
      }  
 }  
 /*  
 *     Split the linked list in half.   
 *     pre: Linked list head  
 *     post: two linked lists. original head: left list.   
 *        returns node pointer to the right list.  
 */  
 template<typename T>  
 Node<T>* splitLinkedlist(Node<T> *head)  
 {  
      if(head == NULL || head->next == NULL)  
           return head;  
      Node<T> * fast = head->next;  
      Node<T> * slow = head;  
      Node<T> * right = NULL;  
      while(fast != NULL && fast->next != NULL)  
      {  
           slow = slow->next;  
           fast = fast->next;  
           fast = fast->next;  
      }  
      right = slow->next;  
      slow->next = NULL;  
      return right;  
 }  
 /*  
 *     merge two sorted linked lists the return head to the sorted list  
 */  
 template<typename T>  
 Node<T>* merge(Node<T>* left, Node<T>* right)  
 {  
      if(left == NULL)  
           return right;  
      if(right == NULL)  
           return left;  
      Node<T> *h = NULL;  
      if(left->data < right->data){  
           h = left;  
           left = left->next;  
      }  
      else{  
           h = right;  
           right = right->next;  
      }  
      Node<T>* t = h;  
      while(left != NULL && right != NULL)  
      {  
           if(left->data < right->data){  
                     t->next = left;  
                     left = left->next;  
                     t = t->next;  
           }  
           else{  
                     t->next = right;  
                     right = right->next;  
                     t = t->next;  
           }  
      }  
      // if any of the list has remaining nodes  
      if(left == NULL)  
           t->next = right;  
      else  
           t->next = left;  
      return h;  
 }  
 /*  
 *     merge sort a linked list  
 */  
 template<typename T>  
 void mergeSort(Node<T>** headref)  
 {  
      Node<T>* head= *headref;  
      if(head == NULL || (head)->next == NULL)  
           return;  
      Node<T>* left = head;  
      Node<T>* right = splitLinkedlist(left);  
      mergeSort(&left);  
      mergeSort(&right);  
      *headref = merge(left, right);  
 }  
 int main()  
 {  
      Node<int>* head = NULL;  
      pushToLinkedList(&head, 5);  
      pushToLinkedList(&head, 15);  
      pushToLinkedList(&head, 11);       
      pushToLinkedList(&head, 8);  
      pushToLinkedList(&head, 17);  
      pushToLinkedList(&head, -1);  
      pushToLinkedList(&head, 4);  
      pushToLinkedList(&head, 20);  
      pushToLinkedList(&head, 11);  
      /*  
      Node<string>* head = NULL;  
      pushToLinkedList(&head, string("David"));  
      pushToLinkedList(&head, string("Alice"));  
      pushToLinkedList(&head, string("Bob"));       
      */  
      cout << "Original List:";   
      printLinkedList(head);  
      mergeSort(&head);  
      cout << "Sorted List:";  
      printLinkedList(head);  
      deleteLinkedList(head);  
      return 0;  
 }