算法打卡Day6

后来，我漂泊他乡，故乡的樱桃却是年年红如故。。。

Leetcode原题

21.合并两个有序链表

思路

其实我本人对链表这一块学得挺模糊的。我们知道链表有分单链表、双链表、循环链表。
单链表的Node数据结构，是一个元素data，和存储指向下一个节点的next。这一道题刚好是单链表入门题。

方法1 循环双指针法

我们可以设立一个哨兵节点result，用于方便返回合并后的链表。并维护一个指针pre，只要不断的操作这个指针，分别比较 l1 和 l2 两个链表头节点的值，谁的值小，pre就将指针指向较小的一方，同时不断的更新l1,l2的节点值。直到l1或l2指向空。在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这时我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

   //循环双指针方法
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 ==null) return l2; //处理空的情况
        if (l2 ==null) return l1;
        
        ListNode resultNode=new ListNode(0);
        ListNode pre =resultNode;
        
        while (l1!=null && l2!=null){
             if (l1.val 
方法2 递归 
参考官网提示，如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。 
    //方法2  递归的形式
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 ==null) return l2; //处理空链表的情况
        if (l2 ==null) return l1;
        if (l1.val 
提交记录
  
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~

算法打卡Day6

Java相关栏目本月热门文章