LeetCode 147 Insertion Sort List

题:

https://leetcode.com/problems/insertion-sort-list/
Sort a linked list using insertion sort.
/** 
 * Definition for singly-linked list. 
 * public class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { 
 *         val = x; 
 *         next = null; 
 *     } 
 * } 
 */  
public class Solution {  
    public ListNode insertionSortList(ListNode head) {  
        if (head == null) return head;  
        // start from second node  
        ListNode node = head.next;  
        ListNode nodePrev = head;  
        while (node != null) {  
            // start from head node  
            ListNode prev = head;  
            ListNode curr = head;  
            while (curr != node) {  
                if (node.val < curr.val) {  
                    // insert node before curr  
                    nodePrev.next = node.next;  
                    node.next = curr;  
                    if (curr == head) {  
                        head = node;  
                    } else {  
                        prev.next = node;  
                    }  
                    node = nodePrev.next;  
                    break;  
                } else {  
                    // continue  
                    prev = curr == head ? head : prev.next;  
                    curr = curr.next;  
                }  
            }  
            if (curr == node) {  
                node = node.next;  
                nodePrev = nodePrev.next;  
            }  
        }  
        return head;  
    }  
}  

作者:ywheel
本文出处:http://blog.ywheel.cn/post/2015/03/12/leetcode_147/
文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。