Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists

注：实现这题我想了两种方法，

1、将ListNode l2中的结点依次插入到l1中去，每次插入后使l1还是有序的

2、使用归并排序在链表上实现的思想

1、

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 != null && l2 != null) {
            while(l2 != null) {
                ListNode p = l1;
                ListNode s = null;
                ListNode q = l2;
                l2 = l2.next;
                while (p != null && p.val <= q.val) {
                    s = p;
                    p = p.next;
                }

                if (p == l1) {
                    q.next = l1;
                    l1 = q;
                } else {
                    q.next = p;
                    s.next = q;
                }
            }
            return l1;
        }
        else if(l1 != null){
            return l1;
        }
        else if(l2 != null){
            return l2;
        }
        else
            return null;
    }
}