Learning Journal

2/3/2024

Insertion Sort List # 3rd attempt

Tags: algorithms leetcode insertion_sort

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */


function insertionSortList(head: ListNode | null): ListNode | null {
    let oldList = head;
    const newList = new ListNode();

    while(oldList !== null) {
        let newListP = newList;
        const curOldP = oldList;

        while(newListP.next !== null && newListP.next.val <= oldList.val){
            newListP = newListP.next;
        }
        


        oldList = oldList.next;

        curOldP.next = newListP.next;
        newListP.next = curOldP;
    }

    return newList.next;
};


/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */


function insertionSortList(head: ListNode | null): ListNode | null {
    let oldList = head;
    const newList = new ListNode();

    while(oldList !== null) {
        let newListP = newList;
        const curOldP = oldList;

        while(newListP.next !== null && newListP.next.val <= oldList.val){
            newListP = newListP.next;
        }
        


        oldList = oldList.next;

        curOldP.next = newListP.next;
        newListP.next = curOldP;
    }

    return newList.next;
};

This is my third time solving this problem.

Here is something I just realized.

Actually, there are 2 linkedlists: the old one and the new one. Our job is to pick the first element of the old one, look for its position in the new one, insert it into that position.

At first, there is not any node in the new one, therefore, we need a dummy node to hold on to it. Then, on the first iteration, because there is no node on the new one, the while loop stop right where it begins. We insert the head of the old node next to the dummy node. Then, on latter iteration, we have something to compare to.

Revised by ChatGPT

This is my third attempt at solving the Insertion Sort List problem.

Here's an insight I've gained:

Essentially, the process involves two linked lists: the original list (old list) and a newly formed list (new list). The task is to sequentially take the first element from the old list, locate the appropriate position for it in the new list, and insert it there.

Initially, the new list is empty, so we introduce a dummy node to serve as its starting point. During the first iteration, since the new list contains no nodes, the while loop terminates immediately. This allows us to place the head of the old list right after the dummy node. In subsequent iterations, the new list has nodes we can compare against, allowing the sorting process to continue effectively.