Leetcode系列之链表（9）

题目：

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的

思路：

普通的排序问题，难点在于探索时间和空间复杂度更优的解法，由于，两个是有序的，较优的解法，可以参考归并排序算法。

代码：

/**

* 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) {

      ListNode resNode = new ListNode(0);

        ListNode cur = resNode;

        while(l1!=null&&l2!=null){

            if(l1.val<=l2.val){

                cur.next = l1;

                cur = cur.next;

                l1 = l1.next;

            }

            else{

                cur.next = l2;

                cur = cur.next;

                l2 = l2.next;

            }

        }

        if(l1!=null){

            cur.next = l1;

        }

        if(l2!=null){

            cur.next = l2;

        }

        return resNode.next;

    }

}