Sort List

Sort List
Sort a linked list in O(n log n) time using constant space complexity.
------------------------------- thinking ----------------------------------------------------------
1. when working on linked list, always remember to cut the node (hdr->next = NULL) when assigning this node to an other list
2. when using merge sort, firstly we should cut out two part lists, or it is easy to jump into a dead loop!!!! Be very careful on dead loop when working on linked list
3. update the next node at the beginning
--------------------------------- codes --------------------------------------------------------

  class Solution {

 public:

     ListNode *sortList(ListNode *head) {

         if (head == NULL || head->next == NULL) {

             return head;

         }

         bool comp_width = true;

         int width = 1;

         while (comp_width) {

             comp_width = false;

             ListNode *top = NULL;

             ListNode *cur = NULL;

             ListNode *rest_hdr = head;

             while (rest_hdr) {

                 ListNode *ahdr = rest_hdr;

                 ListNode *bhdr = find_comp(ahdr, width);

                 if (bhdr) {

                     comp_width = true;

                 }

                 rest_hdr = find_comp(bhdr, width);

                 mrg_sort_list(ahdr, bhdr, &top, &cur);

             }

             head = top;

             width = 2 * width;

         }

         return head;

     }

     ListNode *find_comp(ListNode *hdr, int width) {

         if (hdr == NULL) {

             return NULL;

         }

         int count = 0;

         ListNode *pre = hdr;

         while (count < width && hdr) {

             pre = hdr;

             hdr = hdr->next;

             count++;

         }

         //remember to cut the node before returnning the next list's head

         pre->next = NULL;

         return hdr;

     }

     // bug of using pointer as the input!!!!!

     void mrg_sort_list(ListNode *ahdr, ListNode *bhdr, ListNode **top, ListNode **cur) {

         if (bhdr == NULL) {

             //bug here!!!!!!! we should remember to updata cur

             if (*top) {

                 (*cur)->next = ahdr;

             } else {

                 *top = ahdr;

             }

             return;

         }

         ListNode *anxt = ahdr->next;

         ListNode *bnxt = bhdr->next;

         while (ahdr && bhdr) {

             if (ahdr->val < bhdr->val) {

                 //add ahdr to list

                 anxt = ahdr->next;

                 addhdr(ahdr, top, cur);

                 ahdr = anxt;

             } else {

                 //add bhdr to list

                 //bug here, next node should be at the beginning

                 bnxt = bhdr->next;

                 addhdr(bhdr, top, cur);

                 bhdr = bnxt;

             }

         }

         ListNode *nxt;

             //add ahdr to list

             while (ahdr) {

                nxt = ahdr->next;

                addhdr(ahdr, top, cur);

                ahdr = nxt;

             }

             //add bhdr to list

             while (bhdr) {

                 nxt = bhdr->next;

                addhdr(bhdr, top, cur);

                bhdr = nxt;

             }

     }

     void addhdr(ListNode *hdr, ListNode **top, ListNode **cur) {

         hdr->next = NULL;

         if (*top) {

             (*cur)->next = hdr;

             *cur = hdr;

         } else {

             *top = hdr;

             *cur = hdr;

         }

     }

 };