This is the first day of my participation in the August Text Challenge.More challenges in August

Hi, everybody. Today, I’m going to share with you the next easy problem of LeetCode: Merging two ordered lists.

Here is mainly to share ideas and comments, for everyone to better understand the problem solution, the code part is converted into javascript code by referring to LeetCode,

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.

! [Photo by leetCode]

Example 1: input l1 = 4-trichlorobenzene [1], l2 = [1 4] output:,1,2,3,4,4 [1] example 2: input: l1 = [], l2 = [] output: [] example 3: input: l1 = [], l2 = [0] output: [0]Copy the code

Analysis of the

Analysis of the

1.2 Ascending lists are merged into one ascending list

2. Merge into linked list = “change node pointing

solution

1. The iteration

2. Recursively

Solution a:The iteration

Train of thought1.Define a dummy node as the main axis2.The iteration2A linked list, compare the size3.The smaller ones go into the spindle first4.The rest of the uniterated list needs to be configured */var mergeTwoLists = function (l1, l2) {
  // set a dummy as the main axis
  const dummy = new ListNode(0);

  let cur = dummy;
  // Iterate through l1, l2
  while (l1 && l2) {
    // If l1.val
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
      // And vice versa
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    // Move cur to the next position
    cur = cur.next;
  }

  // If l1 still has a value, l1 has not finished iterating
  while (l1) {
    cur.next = l1;
    cur = cur.next;
    l1 = l1.next;
  }
  // If l2 still has a value, l2 has not finished iterating
  while (l2) {
    cur.next = l2;
    cur = cur.next;
    l2 = l2.next;
  }

  // returns the first node of the main thread
  return dummy.next;
};

/* Complexity time O(n1+n2) n1 is the length of Li and n2 is the length space of L2 O(1) */
Copy the code

Solution two: recursion

Train of thought1.The termination conditions L1 or L2 arenullIs returned when2.Each level of recursion does comparisons and merges */var mergeTwoLists = function (l1, l2) {
  const cur = new ListNode(0);

  function mergeTwoListsRecursive(l1, l2, cur) {
      // If l1 still has a value, l1 has not finished iterating
    if(! l1) {while (l2) {
        cur.next = l2;
        l2 = l2.next;
        cur = cur.next;
      }
      return;
    }
    // If l2 still has a value, l2 has not finished iterating
    if(! l2) {while (l1) {
        cur.next = l1;
        l1 = l1.next;
        cur = cur.next;
      }
      return;
    }

    // Put the smaller ones into the spindle first
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
    mergeTwoListsRecursive(l1, l2, cur);
  }

  mergeTwoListsRecursive(l1, l2, cur);

  return cur.next;
};

/* Complexity time O(n1+n2) n1 is the length of Li and n2 is the length space of L2 O(1) */
Copy the code

conclusion

This question examines the understanding of the ascending combinations of linked lists, with the smaller ones first

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]