<commit_before>/**
 * Sort a linked list using insertion sort.
 * 
 * Tags: Linkedlist, Sort
 */
class InsertionSortList {
    public static void main(String[] args) {
        
    }
    
    /**
     * Check the list one by one to find a node that has smaller value than 
     * nodes before it and swap
     */
    public static ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = new ListNode(0);
        pre.next = head;
		
		/*
		 * pre - check the insertion position from the begining.
		 * p - current element
		 * prev - the element before the current one
		 * c - the p may insert after c.
		 */
        
        for (ListNode p = head.next, prev = head; p != null; prev = p, p = p.next) {// prev -> p
            for (ListNode c = pre; c != prev; c = c.next) {// p is right after prev already.       
                if (c.next.val > p.val) { 
                    prev.next = p.next; // skip p
                    p.next = c.next; // insert between cur and cur.next
                    c.next = p;
                    break;
                }
            }
        }
        return pre.next;
    }
    
    public static class ListNode {
        int val;<commit_msg>Update implementation.<commit_after>/**
 * Sort a linked list using insertion sort.
 * 
 * Tags: Linkedlist, Sort
 */
class InsertionSortList {
    public static void main(String[] args) {
        
    }
    
    /**
     * Check the list one by one to find a node that has smaller value than 
     * nodes before it and swap
     */
    public static ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
		
		/*
		 * dummy - check the insertion position from the begining.
		 * p - current element
		 * pre - the element before the current one
		 * c - the p may insert after c.
		 */
        
        for (ListNode p = head.next, pre = head; p != null; pre = p, p = p.next) {// pre -> p
            for (ListNode c = dummy; c != pre; c = c.next) {//c!=pre because p is right after pre already.       
                if (c.next.val > p.val) {  // ascending sort
                    pre.next = p.next; // skip p
                    p.next = c.next; // insert right after c
                    c.next = p;
                    break;
                }
            }
        }
        return dummy.next;
    }
    
    public static class ListNode {
        int val;
{'fraction_non_alphanumeric': 0.1009861932938856, 'fraction_numerical': 0.0007889546351084812, 'mean_word_length': 1.45024154589372, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4865611', 'n_tokens_mistral': 751, 'n_tokens_neox': 697, 'n_words': 271}