[LeetCode OJ]- Merge 2 Sorted Li

https://leetcode.com/problems/merge-two-sorted-lists/?tab=Description

题目要求是：给定两个已排序的列表，返回一个把这两个列表合并的新的列表。

解题思路：由于两个列表都是已经排好序的，假设是按升序排列的，那么我们可以从头开始取，比较这两个列表l1,l2“最前面”的元素的大小，若l1的最前面的元素小于l2的，那么接下来，把l1的当前比较元素的后一个元素作为此链表”最前面”的元素，再次比较当前l1,l2的最前面的元素的大小，直到他们的最前面元素为空。当有一个链表的最前面元素为空时，这时要返回另一个链表的最前面元素。

可以看出，这是一个recursive的过程，需要不断的重复递归比较的过程，代码如下。

/**

* Definition for singly-linked list.

* public class ListNode {

*    int val;

*    ListNode next;

*    ListNode(int x) { val = x; }

* }

*/

public class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

if(l1==null) return l2;

if(l2==null) return l1;

if(l1.val < l2.val)

{

l1.next = mergeTwoLists(l1.next , l2);

return l1;

}

else

{

l2.next = mergeTwoLists(l1, l2.next);

return l2;

}

}

}