Simple and clean java code


  • 6
    J
    public ListNode insertionSortList(ListNode head) {
    	ListNode cur = head;
    	ListNode dummy = new ListNode(0), p;
    	while (cur != null) {
    		//locate the insertion position.
    		p = dummy;
    		while (p.next != null &&  cur.val > p.next.val) {
    			p = p.next;
    		}
    		//insert between p and p.next.
    		ListNode pNext = p.next;
    		p.next = cur;
    		ListNode next = cur.next;
    		cur.next = pNext;
    		cur = next;
    	}
    	return dummy.next;
    }

  • 0
    This post is deleted!

  • 0
    W

    When you insert between p and p.next, you did not make cur.previous.next = cur.next. I don't understand why it is got accepted. Can someone help me understand it? Thanks!


  • 0
    Y

    Usually we find a descending node first, take it out and insert it into the correct position. But the above snippet actually takes out every single node and insert it, so it's not necessary to make cur.previous.next = cur.next because it's rebuilding the whole list one by one (which is not the best solution).


  • 0
    W

    Got it! Thanks a lot!


Log in to reply
 

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