`

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.

题目的意思是给定两个有序的链表,将它们合并为一个有序的链表。
思路比较简单,依次比较两个节点值得大小,每次取值小的元素挂到新的链表上,下面分别列出递归实现的代码和迭代实现的代码:
递归实现:
/**
 * 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;
        ListNode helper = null;
        if(l1.val > l2.val) {
            helper = l2;
            helper.next = mergeTwoLists(l1, l2.next);
        } else {
            helper = l1;
            helper.next = mergeTwoLists(l1.next, l2);
        }
        return helper;
    }
}


迭代实现:
/**
 * 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;
        ListNode helper = new ListNode(0);
        ListNode head1 = l1;
        ListNode head2 = l2;
        while(l1 != null && l2 != null) {
            if(l1.val > l2.val) {
                helper.next = l2;
                l2 = l2.next;
            } else {
                helper.next = l1;
                l1 = l1.next;
            }
            helper = helper.next;
        }
        while (l1 != null) {
            helper.next = l1;
            l1 = l1.next;
            helper = helper.next;
        }
        while(l2 != null) {
            helper.next = l2;
            l2 = l2.next;
            helper = helper.next;
        }
        return (head1.val > head2.val) ? head2 : head1;
     }
}
分享到:
评论

相关推荐

    程序员面试宝典LeetCode刷题手册

    第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers ...21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli

    MergeTwoSortedLinkedList.java

    【Leetcode】Merge Two Sorted Lists

    leetcode中文版-LeetCode:力码

    21.Merge Two Sorted Lists LeetCode 23.Merge k Sorted Lists(solve1) LeetCode 23.Merge k Sorted Lists(solve2) LeetCode 86.Partition List LeetCode 92.Reverse Linked List II LeetCode 138.Copy List with ...

    cpp-算法精粹

    Merge Two Sorted Lists Merge k Sorted Lists Sort List 快速排序 Sort Colors Kth Largest Element in an Array 桶排序 First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 ...

    lrucacheleetcode-leetcode:leetcode

    lru缓存leetcode leetcode ...Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3

    leetcode双人赛-LeetCode:力扣笔记

    leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring ...Two Sorted ...Merge Two Sorted Lists 简单 链结串列 重要 Remove Duplicates from

    leetcode2sumc-LeetCode:LeetCode的一些题目

    Merge Two Sorted Lists 83 Easy Remove Duplicates from Sorted List 141 Easy Linked List Cycle 160 Easy Intersection of Two Linked Lists 203 Easy Remove Linked List Elements no 206 Easy Reverse Linked ...

    lrucacheleetcode-leetcode-journal:记录所有LeetCode挑战的存储库

    Two Sum (Easy) 2. Add Two Numbers (Medium) 3. Longest Substring Without Repeating Characters (Medium) 7. Reverse Integer (Easy) 21. Merge Two Sorted Lists (Easy) 23. Merge k Sorted Lists (Hard) 31. ...

    leetcode中文版-LeetCode:LeetcodeC++/Java

    leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum 两数之和 array,hash 2 Add Two Numbers 两数相加 math 3 Longest ...Two Sorted ...two ...Merge Two Sorted Lists 合并两个有序链表 lin

    :猴子:LeetCode,剑指提供刷题笔记(C / c++, Python3实现)

    LeetCode 原创文章每周最少两篇,后续最新文章会在首发,视频首发,大家可以加我进交流群,技术交流或提意见都可以,欢迎Star!...Merge Two Sorted Lists 83 * Remove Duplicates from Sorted Lis

    leetcode答案-LeetCode:Swift中的LeetCode

    Merge Two Sorted Lists Easy #26 Remove Duplicates from Sorted Array Easy #27 Remove Element Easy #35 Search Insert Position Easy #38 Count and Say Easy #53 Maximum Subarray Easy #66 Plus One Easy #70 ...

    java二叉树算法源码-algorithm-primer:algorithmprimer-算法基础、Leetcode编程和剑指offer,Ja

    java二叉树算法源码 algorithm-primer algorithm primer - 算法基础、Leetcode编程、剑指offer ...Merge Two Sorted Lists Easy 141 判断链表是是否存在环 Linked List Cycle Easy 142 环形链表II Linked List Cycle I

    leetcode2-Leetcode:Leetcode_answer

    leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。...Merge Two Sorted Lists JavaScript O(n)

    leetcode跳跃-leetcode:leetcode一天一次

    leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum 最长回文:5. Longest Palindromic ...Merge Two Sorted Lists 回文 双指针判断回文:680. 验证回文字符串 Ⅱ

    leetcode中国-cu-cafes:这是一个Java存储库。而CU是楼下的咖啡馆

    leetcode中国 cu-cafes This ...具体内容为(https://leetcode.com/problems/merge-two-sorted-lists/)。其中包含规范代码以及自己写的代码 [模块]: "Merge Two Sorted Lists" 备注:代码使用 Alibab

    leetcode2sumc-ack-CherishLeetCode:ack-CherishLeetCode

    leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。...Merge Two Sorted Lists 83 * Remove Duplicates from Sorted List 141 * Linked List Cycle 160 * Intersection of Two Linke

    leetcode2sumc--Offer:-提供

    leetcode 2 sum c LeetCode 贵有恒,何必三更起五更睡;最无益,只怕一日暴十寒。...Merge Two Sorted Lists 83 * Remove Duplicates from Sorted List 141 * Linked List Cycle 160 * Intersection of Two Linke

    leetcode答案-LeetCode-Trip:LeetCode刷题代码,大佬勿入

    Merge Two Sorted Lists] [53. Maximum Subarray] [70. Climbing Stairs] [101. Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is ...

    leetcode添加元素使和等于-programmer_practices:算法实践

    Merge Two Sorted Lists 22. Generate Parentheses 18 3 sum 扩展版, 外层多套一个循环即可。注意判断重复及细节优化 19 细节:nodelist前插入一个dummy node. 删除倒数第n 等于正数查到len - n 20 用stack 最后...

    javalruleetcode-JavaInterviewChecklist:要检查的Java事项

    Merge Two Sorted Lists 两个链表的交集 Remove Duplicates from Sorted List Palindrome Linked List LL中的插入排序 使用额外的缓冲区从未排序的链表中删除重复项 细绳 确定字符串是否包含所有唯一字符 (CTCI) 在...

Global site tag (gtag.js) - Google Analytics