Insertion Sort List
1093 ワード
Sort a linked list using insertion sort.
挿入順序をlinkedlistの上に適用して、少し小さい変動をします。前に位置を変える要素を探す時、後から一歩前に移動します。singlelinkedlistなので、headから比較して挿入する位置を探す必要があります。
挿入順序をlinkedlistの上に適用して、少し小さい変動をします。前に位置を変える要素を探す時、後から一歩前に移動します。singlelinkedlistなので、headから比較して挿入する位置を探す必要があります。
/**
* 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 p = head==null?null:head.next; //
ListNode previous = head; // p ，previous
while(p!=null){
if(p.valp.val){ // head
previous.next = p.next;
p.next = head;
head = p;
p=previous.next;
}else{
ListNode t = head; // t
while(t.next.val