首页 > 【力扣网练习题】合并两个有序链表

【力扣网练习题】合并两个有序链表

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

示例：输入：1->2->4, 1->3->4

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

解法一：双指针法

  • 时间复杂度：O(a+b) 循环比较两个子问题的次数为 a+b a,b为两个子问题的长度
  • 空间复杂度：O(1) 双指针，常数级别复杂度 
/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*/
/*** @param {ListNode} l1* @param {ListNode} l2* @return {ListNode}*/
var mergeTwoLists = function(l1, l2) {var prevHead = new ListNode(-1);var prevNode = prevHead;while (l1 != null && l2 != null) {if(l1.val <= l2.val){prevNode.next = l1; l1 = l1.next}else{prevNode.next = l2;l2 = l2.next;}prevNode = prevNode.

更多相关：

  • 剑指offer：面试题22. 链表中倒数第k个节点

    题目：链表中倒数第k个节点 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k =...

  • 剑指offer：面试题06. 从尾到头打印链表

    题目：从尾到头打印链表 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1： 输入：head = [1,3,2] 输出：[2,3,1] 限制： 0 <= 链表长度 <= 10000 题目： /*** Definition for singly-linked list.* struct Lis...

  • 删除单链表中的重复节点(c语言版本)

    这是一道经典的面试题，下面是我的研究和举一反三，特整理如下： 分为三种情形: （1）删除有序链表的重复节点，重复节点一个都不留 （2）删除有序链表的重复节点，重复节点只留一个 （3）删除无序链表的重复节点，重复节点只留一个 下面是相关节点的定义： typedef struct ListNode {int val;struc...

  • 链表类型题目需要用到的头文件list.h

    下面是后面链表相关题目中需要用到的链表结点的定义和相关操作函数，参见下面的list.h文件： 注意链表结点的定义采用cpp的定义方式，它会被cpp的文件调用。比如后面删除链表重复结点的文件del_repeated_list.cpp中的编译方式： g++ -g del_repeated_list.cpp -o del_repeate...

©2024 11GX.COM