题目147. Insertion Sort List
Sort a linked list using insertion sort.
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode tempHead = new ListNode(1);
ListNode node = head.next;
tempHead.next = head;
tempHead.next.next = null;
ListNode preNode = null;
ListNode tempNode = null;
ListNode tempNextNode = null;
while(node != null){
tempNextNode = node.next;
int val = node.val;
preNode = tempHead;
tempNode = tempHead.next;
while(tempNode != null){
if(val > tempNode.val){
preNode = tempNode;
tempNode = tempNode.next;
}else{
node.next = preNode.next;
preNode.next = node;
break;
}
}
if(tempNode == null){
node.next = preNode.next;
preNode.next = node;
}
node = tempNextNode;
}
return tempHead.next;
}
}
