C++实现LeetCode(21.混合插入有序链表)

2024-12-02 11:51:53

[LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

这道混合插入有序链表和我之前那篇混合插入有序数组非常的相似 Merge Sorted Array，仅仅是数据结构由数组换成了链表而已，代码写起来反而更简洁。具体思想就是新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾。代码如下：

C++ 解法一：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

Java 解法一：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1), cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

下面我们来看递归的写法，当某个链表为空了，就返回另一个。然后核心还是比较当前两个节点值大小，如果 l1 的小，那么对于 l1 的下一个节点和 l2 调用递归函数，将返回值赋值给 l1.next，然后返回 l1；否则就对于 l2 的下一个节点和 l1 调用递归函数，将返回值赋值给 l2.next，然后返回 l2，参见代码如下：

C++ 解法二：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

Java 解法二：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

下面这种递归的写法去掉了 if 从句，看起来更加简洁一些，但是思路并没有什么不同：

C++ 解法三：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        ListNode *head = l1->val < l2->val ? l1 : l2;
        ListNode *nonhead = l1->val < l2->val ? l2 : l1;
        head->next = mergeTwoLists(head->next, nonhead);
        return head;
    }
};

Java 解法三：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = (l1.val < l2.val) ? l1 : l2;
        ListNode nonhead = (l1.val < l2.val) ? l2 : l1;
        head.next = mergeTwoLists(head.next, nonhead);
        return head;
    }
}

我们还可以三行搞定，简直丧心病狂有木有！

C++ 解法四：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1 || (l2 && l1->val > l2->val)) swap(l1, l2);
        if (l1) l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
};

Java 解法四：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || (l2 != null && l1.val > l2.val)) {
            ListNode t = l1; l1 = l2; l2 = t;
        }
        if (l1 != null) l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
}

到此这篇关于C++实现LeetCode(21.混合插入有序链表)的文章就介绍到这了,更多相关C++实现混合插入有序链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(14.最长共同前缀)

[LeetCode] 14. Longest Common Prefix 最长共同前缀 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: ["flower","flow",&q
C++实现LeetCode(13.罗马数字转化成整数)

[LeetCode] 13. Roman to Integer 罗马数字转化成整数 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D
C++实现LeetCode(16.最近三数之和)

[LeetCode] 16. 3Sum Closest 最近三数之和 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly on
C++实现LeetCode(45.跳跃游戏之二)

[LeetCode] 45. Jump Game II 跳跃游戏之二 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last i
C++实现LeetCode(17.电话号码的字母组合)

[LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合 Given a string containing digits from 2-9inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone butt
C++实现LeetCode(55.跳跃游戏)

[LeetCode] 55. Jump Game 跳跃游戏 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach th
C++实现LeetCode(769.可排序的最大块数)

[LeetCode] 769.Max Chunks To Make Sorted 可排序的最大块数 Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk. After concatenating them,
C++实现LeetCode(12.整数转化成罗马数字)

[LeetCode] 12. Integer to Roman 整数转化成罗马数字 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100
C++实现LeetCode(21.混合插入有序链表)

[LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2
C++实现LeetCode(88.混合插入有序数组)

[LeetCode] 88. Merge Sorted Array 混合插入有序数组 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1and nums2 are m and n respectively. You may assume that nums1 has
C++实现LeetCode(83.移除有序链表中的重复项)

[LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-
C++实现LeetCode(82.移除有序链表中的重复项之二)

[LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp
C++实现LeetCode(23.合并k个有序链表)

[LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这
C++实现LeetCode(109.将有序链表转为二叉搜索树)

[LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary
Java模拟有序链表数据结构的示例

有序链表: 按关键值排序.删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置. 插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1), 如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择优先级队列可以使用有序链表来实现有序链表的插入排序: 对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2) 复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,
JS实现的合并两个有序链表算法示例

本文实例讲述了JS实现的合并两个有序链表算法.分享给大家供大家参考,具体如下: 将两个有序链表合并为一个新的有序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 可以直接运行的方案: <script> function Node(element) { this.element = element;//当前节点的元素 this.next = n
c++如何实现归并两个有序链表

目录归并两个有序链表 1.题目描述 2.设计思路将两个有序链表合并为一个新的有序链表并返回示例在力扣上的提交结果归并两个有序链表 1.题目描述利用基础题里构建的单链表类创建两个有序的整数链表对象,实现将两个有序链表归并成一个新的有序链表并输出该新有序链表的结果.(可以调用已定义的链表类的方法来实现,并注意如何将两个有序的线性表进行归并的算法) 2.设计思路首先通过InputRear()函数构造两个链表,通过不断修改last指针的指向. last->link = newNode; l
C++实现打印两个有序链表公共部分的方法

本文实例讲述了C++实现打印两个有序链表公共部分的方法.分享给大家供大家参考,具体如下: 题目: 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分. 解题思路及代码: 1.head1的值小于head2,则head1往下移动 2.head1的值小于head2,则head2往下移动 3.相等则打印任何一个链表节点的值,head1和head2都往下移动. 4.当head1或head2移动到NULL,终止. 算法C++代码: typedef struct Node { int da

C++实现LeetCode(21.混合插入有序链表)

[LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表

相关推荐

随机推荐