链表插入排序 lintcode-蒲公英云

链表插入排序 lintcode

链表插入排序

难度系数容易通过率 31%

描述
笔记
数据
评测

用插入排序对链表排序

您在真实的面试中是否遇到过这个题？

Yes

样例

Given 1->3->2->0->null, return 0->1->2->3->null

package tju.cs.bigdata.chc;
public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
    public ListNode createList(String s){
        ListNode res = new ListNode(-1);
        String[] strings = s.split("->");
        ListNode cur = res;
        for(String st : strings){
            if(!st.equals("null"))cur.next = new ListNode(Integer.parseInt(st));
            cur = cur.next;
        }
        return res.next;
    }
    public void printList(ListNode l){
        ListNode cur = l;
        if(l == null)return;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
}
package tju.cs.bigdata.chc;
public class InsertionSortList {
       public ListNode insertionSortList(ListNode head) {
            // write your code here
            if(head == null || head.next == null){
                return head;
            }
            ListNode res = new ListNode(-1);
            ListNode cur = head;
            ListNode curtmp = res;
            while(cur != null){
                curtmp = res;
                while(curtmp.next != null && curtmp.next.val <= cur.val){
                    curtmp = curtmp.next;
                }
//                curtmp.printList(curtmp);
//                cur.printList(cur);
                ListNode l = cur.next;
                cur.next = curtmp.next;
                curtmp.next = cur;
                cur = l;
//                if(cur != null)cur.printList(cur);
//                curtmp.printList(curtmp);
            }        
            return res.next;
        }
       public static void main(String[] args){
           String string = "1->3->2->0->null";
           ListNode res = new ListNode(-1).createList(string);
           res.printList(res);
           InsertionSortList insertionSortList = new InsertionSortList();
           ListNode res1 = insertionSortList.insertionSortList(res);
           res1.printList(res1);
       }
}