剑指offer Linked List

剑指offer-合并两个排序的链表

Posted by franki on May 1, 2021

合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增顺序的。

思路

1 链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点是合并后链表的头结点

2 在剩余的结点中，链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是剩余节点的头结点，把这个节点和之前已经合并好的链表的尾结点链接起来

代码

var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    }
    if (l2 === null) {
        return l1;
    }
    let mergedLinkedList = null;
    if (l1.val < l2.val) {
        mergedLinkedList = l1;
        mergedLinkedList.next = mergeTwoLists(l1.next, l2);
    } else {
        mergedLinkedList = l2;
        mergedLinkedList.next = mergeTwoLists(l1, l2.next);
    }
    return mergedLinkedList;
};

复杂度分析

  • 时间复杂度: O(N)
  • 空间复杂度: O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS