insertion sort list


  • 0

    public class Solution {
    /**
    * @param head: The first node of linked list.
    * @return: The head of linked list.
    */
    public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) {
    return head;
    }

        ListNode sortedListHead = new ListNode(0);//dummy head
        ListNode pre,curr,next;
        curr = head;
        
        while (curr != null) {// insert every single curr into sorted list
            next = curr.next; //prepare for insertion && swapping.
            pre = sortedListHead;//the list to scan
            while (pre.next != null && pre.next.val <= curr.val) {
                //as long as pre and its front are sorted ascending, keep going
                pre = pre.next;
            }
            //when pre.next == null , or curr is less than a node in pre.next, we want to insert curr before that pre.next node
            curr.next = pre.next;
            pre.next = curr;
            
            curr = next;//use the original next, instead of the new curr.next
        }//end while
        
        return sortedListHead.next;
    }
    

    }

    /*
    Thoughts:
    Look at head pointer, which is the current element we focus on.
    If it's greater than the next pointer value, we move on. Use a while loop to check the entire
    list every time with a new head.
    If the head.val is less/equal than the next.val, we stop the at this next pointer, then cut it,
    insert head.
    /
    /
    *

    • Definition for ListNode.
    • public class ListNode {
    • int val;
      
    • ListNode next;
      
    • ListNode(int val) {
      
    •     this.val = val;
      
    •     this.next = null;
      
    • }
      
    • }
      /
      public class Solution {
      /
      *
      • @param head: The first node of linked list.
      • @return: The head of linked list.
        */
        public ListNode insertionSortList(ListNode head) {
        if (head == null) {
        return null;
        }
        ListNode dummy = new ListNode(0);
        while (head != null) {
        ListNode node = dummy;
        while (node.next != null && node.next.val < head.val) {
        node = node.next;
        }
        ListNode temp = head.next;
        head.next = node.next;
        node.next = head;
        head = temp;
        }
        return dummy.next;
        }
        }

Log in to reply
 

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