第33天--算法（Leetcode 148）
148.排序链表
public ListNode sortList(ListNode head) { ListNode cur = head; int length = 0; while(cur != null) { cur = cur.next; length ++; } ListNode h = head; ListNode teamFirst = head; ListNode teamLast = null; for(int eachLen = 1;eachLen < length;eachLen <<= 1) { while(teamFirst != null) { ListNode ht[] = hthtn(teamFirst,eachLen); ListNode m[] = merge(ht[0],ht[1],ht[2],ht[3]); if(h == teamFirst) { h = m[0]; teamLast = m[1]; }else { teamLast.next = m[0]; teamLast = m[1]; } teamFirst = ht[4]; } teamFirst = h; teamLast = null; } return h; } public ListNode[] hthtn(ListNode teamFirst,int eachLen) { ListNode l1 = teamFirst; ListNode r1 = teamFirst; ListNode l2 = null; ListNode r2 = null; ListNode next = null; int pass = 0; while(teamFirst != null) { pass ++; if(pass <= eachLen) { r1 = teamFirst; } if(pass == eachLen + 1) { l2 = teamFirst; } if(pass > eachLen) { r2 = teamFirst; } if(pass == (eachLen << 1)) { break; } teamFirst = teamFirst.next; } r1.next = null; if(r2 != null) { next = r2.next; r2.next = null; } return new ListNode[] {l1,r1,l2,r2,next}; } public ListNode[] merge(ListNode ls,ListNode le,ListNode rs,ListNode re) { if(rs == null) { return new ListNode[] {ls,le}; } ListNode head = null; ListNode tail = null; ListNode pre = null; ListNode cur = null; while(ls != le.next && rs != re.next) { if(ls.val <= rs.val) { cur = ls; ls = ls.next; }else { cur = rs; rs = rs.next; } if(pre == null) { head = cur; pre = cur; }else { pre.next = cur; pre = pre.next; } } if(ls != le.next) { while (ls != le.next) { pre.next = ls; pre = pre.next; tail = ls; ls = ls.next; } }else { while (rs != re.next) { pre.next = rs; pre = pre.next; tail = rs; rs = rs.next; } } return new ListNode[] {head,tail}; }