当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.021.Merge Two Sorted Lists

LeetCode.021.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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解题过程

循环法

这是之前做过的一道题,非常简单,也没啥注意事项,写完一次AC,调都不用调:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null || l2==null)
            return l1==null ? l2 : l1;
        ListNode p1=l1, p2=l2, res, resHead;
        if(p1.val<p2.val){
            resHead = res = p1;
            p1 = p1.next;
        }else{
            resHead = res = p2;
            p2 = p2.next;
        }
        while(p1!=null && p2!=null){
            if(p1.val<p2.val){
                res.next = p1;
                p1 = p1.next;
            }else{
                res.next = p2;
                p2 = p2.next;
            }
            res = res.next;
        }
        res.next = p1==null ? p2 : p1;
        return resHead;
    }
}

递归法

讨论区排第一位的是一个递归解法,代码很简洁:

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(l2.next, l1);
            return l2;
        }
    }
};

不过评论中好几个说有栈溢出风险。


GitHub代码


上一篇 LeetCode.020.Valid Parentheses

下一篇 LeetCode.014.Longest Common Prefix

阅读
273
阅读预计1分钟
创建日期 2018-02-09
修改日期 2018-02-09
类别
百度推荐