[LintCode] 219 Insert Node in Sorted Linked List

Description
Insert a node in a sorted linked list.


Example
Given list = 1->4->6->8 and val = 5.
Return 1->4->5->6->8.


思路
找到相应的位置，并插入这个点。（用dummy node。因为可能插在第一个位置的前面。）
过一遍例子：
0->1->4->6->8->null （当前位置在0，比下一位的值1和插入值5。接着往下走。）
0->1->4->6->8->null（当前位置在1，比下一位的值4和插入值5。接着往下走。）
0->1->4->6->8->null（当前位置在4，比下一位的值6和插入值5。发现6比5大。说明要插在6前面。停止循环。）
我们这时候知道6前面的位置。于是很好办了。插入后链表变成0->1->4->5->6->8->null
最后返回dummy的下一个位置。


Code

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param head: The head of linked list.
     * @param val: an integer
     * @return: The head of new linked list
     */
    public ListNode insertNode(ListNode head, int val) { 
        // Write your code here
        if (head == null) {
            return new ListNode(val);
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while (head.next != null && head.next.val < val) {
            head = head.next;
        }
        ListNode node = new ListNode(val);
        node.next = head.next;
        head.next = node;
        return dummy.next;
    }  
}