• leetcode 21


    21. 合并两个有序链表

    描述

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

    示例 1:
    输入:l1 = [1,2,4], l2 = [1,3,4]
    输出:[1,1,2,3,4,4]

    示例 2:
    输入:l1 = [], l2 = []
    输出:[]

    示例 3:
    输入:l1 = [], l2 = [0]
    输出:[0]

    法一

    /**
     * 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 list1, ListNode list2) {
            if (list1 == null) {
                return list2;
            } else if (list2 == null) {
                return list1;
            } else if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    算法实现

    终止条件:当两个链表都为空时,表示我们对链表已合并完成。
    如何递归:我们判断 list 1 和 list 2 头结点哪个更小,然后较小结点的 next 指针指向其余结点的合并结果。(调用递归)

    法二

    /**
     * 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 list1, ListNode list2) {
            ListNode head = new ListNode();
            ListNode last = head;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    last.next = list1;
                    list1 = list1.next;
                } else {
                    last.next = list2;
                    list2 = list2.next;
                }
                last = last.next;
    
            }
            if (list1 != null)last.next = list1;
            if (list2 != null) last.next = list2;
            return head.next;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    算法实现

    捋一捋题意: 1. 给你两个有序链表 2. 合并为一个有序链表

    可以简单理解为: 同时遍历两个链表, 当前遍历的结点,谁的结点小,就把谁的结点“摘下来”,“安装”在新链表上就可以了吧。

    这里为了简单方便的处理, 给新链表先“安装”一个头结点,然后比如例一:

    将 l2 链表的 1 结点摘下来,放到新链表的尾部。
    将 l1 链表的 1 结点摘下来,放到新链表的尾部。
    将 l1 链表的 2 结点摘下来,放到新链表的尾部。 同理…
    最后l2 链表被摘完了, l2 == null ,l1 链表剩下的部分,“安装”在新链表的尾部。

  • 相关阅读:
    Python学习记录(4)元组:戴了紧箍咒的列表
    物联网行业数字化转型CRM解决方案
    gin框架再探
    指针传2
    【软件工程之美 - 专栏笔记】35 | 版本发布:软件上线只是新的开始
    【HMS core】【Ads Kit】华为广告——海外应用在国内测试正式广告无法展示
    【笔记】KMeans聚类算法
    windows10不支持Miracast无线投屏(不能进行无线投影)
    自控力前言
    页面交互(js与HTML,css的使用)
  • 原文地址:https://blog.csdn.net/starry_night_summer/article/details/127816944