景歳のLeetcode解題報告:147.Insertion Sort List (Java)
この問題はチェーンテーブルの挿入ソートを要求しており,チェーンテーブルの操作を簡単に考察する問題である.難点は、ソートされていないノードがソートされたノードを挿入する場合の3つの違いです.
1ソートされた部分の先頭ノードが挿入する値より大きい2ソートされた部分の最後のノードが挿入する値より小さい3の中間の場合:挿入する値がソートされた値の中間にある
次の手順は、ソートを挿入する内層サイクルで、上記の3つの状況をそれぞれ処理します.
1ソートされた部分の先頭ノードが挿入する値より大きい2ソートされた部分の最後のノードが挿入する値より小さい3の中間の場合:挿入する値がソートされた値の中間にある
次の手順は、ソートを挿入する内層サイクルで、上記の3つの状況をそれぞれ処理します.
/**
* 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||head.next==null){ // ，
return head;
}
ListNode lh=head;
ListNode rh=head.next;
head.next=null;
ListNode temp1=null;
ListNode temp2=null;
//
while(rh!=null){
lh=head;
//
while(lh.val=rh.val){
head=rh;
head.next=lh;
}
else{
temp1.next=rh;
rh.next=lh;
}
// rh temp2 rh.next
rh=temp2;
}
return head;
}
}