Linked List Insertion Sort

listsort.java

/**
 * https://oj.leetcode.com/problems/insertion-sort-list/
 * 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) {
        ListNode n = head;        
        while (n != null && n.next != null) {
            ListNode target = n.next;
            if (n.val > target.val) {
                n.next = target.next;
                head = findAndReplace(head, target);
            } else
                n = n.next;
        }
        return head;
    }
    public ListNode findAndReplace(ListNode head, ListNode target) {
        ListNode n = head;
        ListNode prev = null;
        while(n != null) {
            if(n.val > target.val ) {
            	target.next = n;
            	if(prev == null)
            		head = target;
            	else
            		prev.next = target;
            	break;
            }
            prev = n;
            n = n.next;
        }
        return head;
    }
}

https://oj.leetcode.com/problems/insertion-sort-list/