1     public ListNode sortList(ListNode head) { 2         ListNode tail , p, q, e; 3         int  insize, merges, psize, qsize, i; 4         if (head == null) return null;  5          6  7         insize = 1; 8         while (true) { 9             p = head;10             head = null;11             tail  = null;12 13             merges = 0;14 15             while (p != null) {16 17                 merges++;18                 q = p;19                 psize = 0;20                 for (i = 0; i < insize; i++) {21                     psize++;22                     q = q.next;23                     if (q == null) break;24                 }25 26                 qsize = insize;27                 while (psize > 0 || (qsize > 0 && q != null)) {28                     if (psize == 0) {29                         e = q; q = q.next; qsize--;30                     } else if(qsize == 0 ||  q == null) {31                         e = p; p = p.next; psize--;32                     } else if ((p.val - q.val) <= 0) {33                         e = p; p = p.next; psize--;34                     } else {35                         e = q; q = q.next; qsize--;36                     }37 38                     if (tail != null) {39                         tail.next = e;40                     } else {41                         head = e;42                     }43 44                     tail = e;45                 }46 47                 p = q;48             }49 50             tail.next = null;51 52             if (merges <= 1) return head;53 54             insize *= 2; 55         }56     }