25. 合并两个排序的链表(面试)youif的博客-面试题25:合并两个排序的链表 空间复杂度

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

两个有序链表的排序，实际上可以看成一个单链表使用归并排序的最后一个环节：“将两个排好序的子序列合并为一个子序列：每次都是从未比较的两个子序列的最小值中选出一个更小值”。

遍历实现

package 剑指offer.合并两个排序的链表_25;/* 作者     :XiangLin 创建时间 :16/06/2020 17:12 文件     :Solution.java IDE      :IntelliJ IDEA */ public class Solution { public static class ListNode{ int val;         ListNode next; public ListNode(int val){ this.val = val; } } public ListNode mergeTowLists(ListNode L1,ListNode L2){         ListNode temp = new ListNode(0);         ListNode head = temp;//保留头节点的引用 while (L1 != null && L2 != null){ if (L1.val < L2.val){                 temp.next = L1;                 L1 = L1.next; }else {                 temp.next = L2;                 L2 = L2.next; }             temp = temp.next; } if (L1 == null) temp.next = L2;//l1子序列为空，则直接拼届l2 if (L2 == null) temp.next = L1; return head.next;//返回头节点指向的序列 } } 

递归实现

package 剑指offer.合并两个排序的链表_25;/* 作者     :XiangLin 创建时间 :16/06/2020 17:33 文件     :Solution1.java IDE      :IntelliJ IDEA */ public class Solution1 { public static class ListNode{ int val;         ListNode next; public ListNode(int val){ this.val = val; } } public ListNode merger(ListNode L1,ListNode L2){ if (L1 == null){ return L2; } if (L2 == null){ return L1; } if (L1.val <= L2.val){             L1.next = merger(L1.next,L2); return L1; }else {             L2.next = merger(L2.next,L1); return L2; } } } 

另外博主这些年来看过或者听过的一些不错的常用的上千本书籍，没准你想找的书就在这里呢，包含了互联网行业大多数书籍和面试经验题目等等。有人工智能系列（常用深度学习框架TensorFlow、pytorch、keras。NLP、机器学习，深度学习等等），大数据系列(Spark,Hadoop,Scala,kafka等)，程序员必修系列（C、C++、java、数据结构、linux，设计模式、数据库等等）以下是部分截图

更多文章见本原创微信公众号「五角钱的程序员」，我们一起成长，一起学习。一直纯真着，善良着，温情地热爱生活。关注回复【电子书】即可领取哦。

给大家推荐一个Github,上面非常非常多的干货：https://github.com/XiangLinPro/IT_book