链表插入排序 lintcode

ゝ一纸荒年。 2022-07-16 12:09 201阅读 0赞

####  链表插入排序 ####

难度系数 容易 通过率 31%

*  [ 描述][Link 1]
 *  [ 笔记][Link 2]
 *  [ 数据][Link 3]
 *  [ 评测][Link 4]

用插入排序对链表排序

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

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);
    	   }
    }

[Link 1]: http://www.lintcode.com/zh-cn/problem/insertion-sort-list/#description
[Link 2]: http://www.lintcode.com/zh-cn/problem/insertion-sort-list/#note
[Link 3]: http://www.lintcode.com/zh-cn/problem/insertion-sort-list/#testcase
[Link 4]: http://www.lintcode.com/zh-cn/problem/insertion-sort-list/#judge