Implement a 15-Line C# Solution Without Helper Node


  • 0
    L
    public ListNode InsertionSortList(ListNode head) {
        for (ListNode iNode = head; iNode != null; iNode = iNode.next)
            for (ListNode pre = head, jNode = head, tmp = jNode.next; jNode != iNode && jNode.next != null; tmp = jNode.next)
                if (jNode.val > jNode.next.val){
                    jNode.next = tmp.next;
                    tmp.next = jNode;
                    if (pre == jNode) head = pre = tmp;
                    else{
                        pre.next = tmp;
                        pre = tmp;
                    }
                }else{
                    pre = pre == jNode ? pre : pre.next;
                    jNode = pre.next;
                }
        return head;
    }

  • 0
    L
    This post is deleted!

  • 0
    L

    This is closer to the original Pseudo code on WikiPedia https://en.wikipedia.org/wiki/Insertion_sort

    Pseudocode of the complete algorithm follows, where the arrays are zero-based:[1]:116

    for i ← 1 to length(A) - 1
        j ← i
        while j > 0 and A[j-1] > A[j]
            swap A[j] and A[j-1]
            j ← j - 1
        end while
    end for

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.