147. Insertion Sort List【M】Java

class Solution(object):def insertionSortList(self, head):if head == None or head.next == None:return headhelper = ListNode(0)cur = head #the node will be insertedpre = helper # insert the node after prenext = None # the next node will be insertedwhile cur:next = cur.nextwhile pre.next and pre.next.val < cur.val:pre = pre.nextcur.next = pre.nextpre.next = curpre = helpercur = nextreturn helper.next

public class Solution {public ListNode insertionSortList(ListNode head) {if( head == null ){return head;}ListNode helper = new ListNode(0); //new starter of the sorted listListNode cur = head; //the node will be insertedListNode pre = helper; //insert node between pre and pre.nextListNode next = null; //the next node will be inserted//not the end of input listwhile( cur != null ){next = cur.next;//find the right place to insertwhile( pre.next != null && pre.next.val < cur.val ){pre = pre.next;}//insert between pre and pre.nextcur.next = pre.next;pre.next = cur;pre = helper;cur = next;}return helper.next;}
}