This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

In data structures and algorithms, a linked list is a non-sequential and non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list. There are many different types of linked lists: unidirectional, bidirectional and circular. Linked lists can be implemented in many programming languages.

A linked list consists of a series of nodes (nodes). Each node consists of two parts: a data field that stores data elements and a pointer field that stores the address of the next node.

Linked lists allow insertion and removal of nodes at any location on the table, but do not allow random access. Because they do not have to be stored sequentially, linked lists can be O(1) complexity when inserted, but O(n) time is required to find a node or access a node with a specific number.

Let’s go through a LeetCode problem to understand the characteristics and applications of linked lists.

The title

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]Copy the code

Example 2:

Input: L1 = [], L2 = [] output: []Copy the code

Example 3:

Input: L1 = [], L2 = [0] output: [0]Copy the code

Tip:

  • The number of nodes in two linked lists ranges from 0 to 50.

  • -100 <= Node.val <= 100

  • Both L1 and L2 are arranged in non-decreasing order

thinking

For this problem, the first thing that can be thought of is that we compare the two linked list nodes one by one, taking out the smaller node each time, and then continue to compare the remaining nodes. It’s not that hard to think about, so how do I write the code? We can write code by recursion.

Also, consider the boundary case. If there is an empty list, we just need to return a non-empty list. If either list is empty, the recursion ends.

Here’s the code.

answer

recursive

/ * * *@author A hackney-coach *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
  if (l1 === null) { // The L1 node is empty
    return l2;
  } else if (l2 === null) { // L2 is empty
    return l1;
  } else if (l1.val < l2.val) { // Fetch the smaller node
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else { // Fetch the smaller node
    l2.next = mergeTwoLists(l1, l2.next);
    returnl2; }};Copy the code

Complexity analysis:

  • Time complexity: O(n + m), where n and M are the lengths of two linked lists respectively.

  • Space complexity: O(n + m).

reference

  • 21. Merge two ordered lists