每日算法----合并两个有序链表----2020105 （34）（补）

目录

1. 题目描述2. 示例3. 思路4. 遇上的问题5. 具体实现代码6. 学习收获,官方一如既往的妙啊7 题目来源

1. 题目描述

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

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2. 示例

3. 思路

新建一个节点，比较传入的节点值，取小的值赋予新节点，递归调用小值的下一个节点和另一个不变的节点，出口是比较结束返回新建节点。

4. 遇上的问题

emm，问题是每次递归多增加了一个节点，导致空间消耗增加，解决办法可以直接返回比较后小的节点，这样之后可能就是消耗的。

5. 具体实现代码

自己写的代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //如果结果为空，直接返回另一个节点 if(l1==null){ return l2; } if(l2==null){ return l1; } //这里新建节点用于保存，对链表结构掌握不清晰，可以直接修改next指针 ListNode node = new ListNode(); if(l1.val>=l2.val){ node.val = l2.val; node.next = mergeTwoLists(l1,l2.next); } if(l1.val<l2.val){ node.val = l1.val; node.next = mergeTwoLists(l1.next,l2); } return node; } }

6. 学习收获,官方一如既往的妙啊

官方算法–迭代

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //编写头节点 ListNode prehead = new ListNode(-1); //赋值，作用是用于循环。 ListNode prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { // prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev.next = l1 == null ? l2 : l1; //返回头结点之后的链表 return prehead.next; }

执行时间很快，迭代比递归快，耗费内存比较多，官方的递归也做得比我好，空间方面比我节省。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { //在这里并没有直接赋新值，而是改变每个节点的next尾巴， //让next指向下一个比它小的数值！妙啊！ l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }

7 题目来源

leetCode

---

妙得一塌糊涂，哈哈哈哈！------swrici