Cacher is the code snippet organizer for pro developers

//T O(n)
//S O(1) heap: O(1), stack O(1)
/* Key: target.next = prev.next;
     prev.next = target; 
先把目标指向右边node 再把左边node指向目标*/

public class Solution {
    public ListNode insertNode(ListNode head, int target) {
        ListNode newNode = new ListNode(target);
        //corner case : if the target is smaller than head, insert it before head(let it point to head)
        if(head== null || target < head.value){
            newNode.next = head;
            return newNode;
        }
        /* use a pointer "previous" to traverse the linkedlist,
        compare target with the value of prev.next node 
        until we find the target is smaller than prev.next.
        after the traverse, the target should be inserted between prev and prev.next
         */
        ListNode prev = head;
        //corner case 2: stop if prev.next reach the end
        while(prev.next!= null && prev.next.value< target){
            prev = prev.next;
        }
        newNode.next = prev.next;
        prev.next = newNode;
        //return head becuase the target is not case 1.
        return head;
    }
  }