A direct way without helper node to sort in JAVA


  • 0
    J

    It is a direct way to sort the given list without helper node. While we traverse the list, we always maintain the head of the list and insert the node in proper position. The code is as follow:

    public ListNode insertionSortList(ListNode head) {

       if(head == null || head.next == null)  return head;
        ListNode cur = head.next;
        ListNode pre = head;
        while(cur != null) {
            //
            if(cur.val >= pre.val)  {
                pre = cur;
                cur = cur.next;
                continue;
            } 
            //
            ListNode cur1 = head;
            ListNode pre1 = head;
            while(cur1.val <= cur.val) {
                if(pre1 == cur1)  cur1 = cur1.next;
                else {
                    pre1 = cur1;
                    cur1 = cur1.next;
                }
            }
            
            pre.next = cur.next;
            if(cur1 == head) {
                cur.next = head;
                head = cur;
            }else {
                pre1.next = cur;
                cur.next = cur1;
            }
            cur = pre.next;
        }
        //
        return head;
    }

  • 0
    X

    @jumperque
    would you mind explaining the following code.
    //
    ListNode cur1 = head;
    ListNode pre1 = head;
    while(cur1.val <= cur.val) {
    if(pre1 == cur1) cur1 = cur1.next;
    else {
    pre1 = cur1;
    cur1 = cur1.next;
    }
    }


  • 0
    X

    @xiaowu4 I see. the pre1 means we should insert node previous .and cur1 means the next.
    You should be make a good name for the variable.


Log in to reply
 

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