Insertion Sort Listチェーンテーブル挿入ソート@LeetCode

原理は簡単で、挿入ソートですが、チェーンテーブルの性質のため、挿入の位置を前から後ろに探さなければなりません.
しかし、いろいろなバグがありやすく、一度にバグフリーを作るのは難しい.

package Level4;

import Utility.ListNode;

/**
 * Insertion Sort List 
 * 
 *  Sort a linked list using insertion sort.
 *
 */
public class S135 {

	public static void main(String[] args) {
		ListNode head = new ListNode(4);
		ListNode n2 = new ListNode(2);
		ListNode n3 = new ListNode(1);
		ListNode n4 = new ListNode(3);
		ListNode n5 = new ListNode(1);
		head.next = n2;
		n2.next = n3;
		n3.next = n4;
//		n4.next = n5;
//		ListNode ret = insertionSortList(head);
//		ret.print();
		
		int[] list = {-84,142,41,-17,-71,170,186,183,-21,-76,76,10,29,81,112,-39,-6,-43,58,41,111,33,69,97,-38,82,-44,-7,99,135,42,150,149,-21,-30,164,153,92,180,-61,99,-81,147,109,34,98,14,178,105,5,43,46,40,-37,23,16,123,-53,34,192,-73,94,39,96,115,88,-31,-96,106,131,64,189,-91,-34,-56,-22,105,104,22,-31,-43,90,96,65,-85,184,85,90,118,152,-31,161,22,104,-85,160,120,-31,144,115};
//		int[] list = {1,0,2,1};
//		int[] list = {1,2,-1,0};
		ListNode dum = ListNode.create(list);
//		dum.print();
		
		ListNode ret = insertionSortList(dum);
		ret.print();
	}
	
	public static ListNode insertionSortList(ListNode head) {
        if(head==null || head.next==null){
        	return head;
        }
        
        ListNode p = head;		//       
        ListNode q = head.next;
        
        while(p!=null && q!=null){
        	if(p.val <= q.val){	//     ，    ，      
        		p = q;
        		q = q.next;
        	}else{			// out of order！
        		ListNode h = head;
        		if(head.val >= q.val){		// q   head       
        			ListNode qnext = q.next;
        			p.next = qnext;
        			q.next = head;
        			head = q;		//      
        			q = qnext;		//   q   ， q      
        		}else{
        			while(h.val<=q.val && h.next.val<=q.val){	//  head   ，        q  ，         ！
        				h = h.next;
        			}
        			if(h.val<=q.val && q.val<=h.next.val){		//  q         
        				ListNode qnext = q.next;
        				p.next = qnext;
        				q.next = h.next;
        				h.next = q;
        				q = qnext;		//   q   ， q      
        			}
        		}
        	}
        }
        
        return head;
    }
}

以下は、dummyノードを構築し、dummyノードから秩序チェーンテーブルを構築する簡単な方法です.すなわち、headをヘッダとする無秩序チェーンテーブルと、dummyをヘッダとする秩序チェーンテーブルの2つがあります.プロセスは、順序付きチェーンテーブルを最初から巡回するたびに、無秩序なチェーンテーブルヘッダの挿入に適した次の場所を見つけることです.最終的にすべての無秩序チェーンテーブルが秩序チェーンテーブルに移行した.

/**
 * 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 dummy = new ListNode(0); // From dummy node, we will create a sorted linkedlist
        
        ListNode cur = head;
        while(cur != null) {
            ListNode pre = dummy;   // pre is used to find the place to insert
            while(pre.next!=null && cur.val>pre.next.val) { // find the element which small enough to be inserted
                pre = pre.next;
            }
            ListNode next = cur.next;   // unlink from unorder linkedlist and link to order linkedlist
            cur.next = pre.next;
            pre.next = cur;
            cur = next;
        }
        return dummy.next;
    }
}