2015年10月15日星期四

Leetcode 147 Insertion Sort List

Sort a linked list using insertion sort.
Solution 1: insertion sort, use dummy node.
 public class Solution {  
   public ListNode insertionSortList(ListNode head) {  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode i=dummy;  
     while (i.next!=null) {  
       if (i==dummy || i.next.val>=i.val) i=i.next;  
       else {  
         ListNode j=dummy;  
         while (j.next.val<i.next.val) j=j.next;  
         ListNode p=i.next;  
         i.next=p.next;  
         p.next=j.next;  
         j.next=p;  
       }  
     }  
     return dummy.next;  
   }  
 }  

没有评论:

发表评论