合并两个有序链表(Java实现)

简介: 合并两个有序链表(Java实现)

合并两个有序链表(Java实现)


题目:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。


示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

解法一:常规解法

package Day47;
/**
 * @Author Zhongger
 * @Description 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * @Date 2020.3.20
 */
public class MergeTwoListsSolution {
    public static void main(String[] args) {
        ListNode l1_1 = new ListNode(1);
        ListNode l1_2 = new ListNode(2);
        ListNode l1_3 = new ListNode(4);
        l1_1.next=l1_2;
        l1_2.next=l1_3;
        ListNode l2_1 = new ListNode(1);
        ListNode l2_2 = new ListNode(3);
        ListNode l2_3 = new ListNode(4);
        l2_1.next=l2_2;
        l2_2.next=l2_3;
        MergeTwoListsSolution solution = new MergeTwoListsSolution();
        ListNode mergeTwoLists = solution.mergeTwoLists(l1_1, l2_1);
        ListNode temp=mergeTwoLists;
        while (temp!=null){
            System.out.println(temp);
            temp=temp.next;
        }
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1==null&&l2==null){
            return null;
        }
        ListNode resList=new ListNode(0);//头结点
        ListNode temp=resList;//辅助节点
        while (l1!=null&&l2!=null){
            if (l1.val<l2.val){
                temp.next=new ListNode(l1.val);
                l1=l1.next;
            }else {
                temp.next=new ListNode(l2.val);
                l2=l2.next;
            }
            temp=temp.next;
        }
        if (l1==null){
            temp.next=l2;
        }
        if (l2==null){
            temp.next=l1;
        }
        return resList.next;
    }
}
class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    @Override
    public String toString() {
        return  val+" ";
    }
}

解法二:递归解法

 /**
     * 递归求解
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

关于递归求解的方法,可以查看该链接。https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/yi-kan-jiu-hui-yi-xie-jiu-fei-xiang-jie-di-gui-by-/


相关文章
|
3月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
59 0
Leetcode第21题(合并两个有序链表)
|
3月前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
55 3
|
3月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
129 0
|
5月前
|
Python
【Leetcode刷题Python】21. 合并两个有序链表
介绍了几种不同的方法来合并多个已排序的链表,包括暴力求解、使用小顶堆以及分而治之策略。
54 2
|
3月前
|
存储 Java 开发者
HashSet和TreeSet教你重新认识Java集合的无序与有序
【10月更文挑战第14天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了它们分别实现无序和有序存储的机制。通过理解HashSet基于哈希表的无序特性和TreeSet利用红黑树实现的有序性,帮助开发者更好地选择合适的集合类型以满足不同的应用场景。
48 2
|
4月前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
3月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
31 3
|
5月前
|
存储 Java
|
6月前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
48 8
【数据结构OJ题】合并两个有序链表
|
5月前
|
算法
LeetCode第21题合并两个有序链表
该文章介绍了 LeetCode 第 21 题合并两个有序链表的解法,通过创建新链表,依次比较两个链表的头节点值,将较小的值插入新链表,直至其中一个链表遍历完,再将另一个链表剩余部分接到新链表后面,实现合并。
LeetCode第21题合并两个有序链表

热门文章

最新文章