[LeetCode OJ]- Merge 2 Sorted Li
2017-03-07 本文已影响0人
其中一个cc
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;
}
}
}
