loading...

Merging Sorted Lists, Two Ways

alisabaj profile image Alisa Bajramovic Updated on ・9 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm of the day is the Merge Two Sorted Lists problem:

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

For example, if the first list was 1 > 3 > 5 and the second list was 1 > 4 > 6, the output of the function should be 1 > 1 > 3 > 4 > 5 > 6.

This algorithm is often solved iteratively and recursively, so in this blog post I'll be walking through both solutions. Before I get to the solutions, though, I'll explain what recursion and iteration are, and why they'd be useful in this kind of problem.

Recursion and Iteration: What are They?

"Recursion" and "iteration" are two terms that are often used when describing how to approach an algorithm, and they're often used in comparison.

Iteration means you'll be looping over your code. For example, you'll be writing a while loop or a for loop, and as long as the condition remains true, your function will continue to execute a certain task.

Recursion means you'll be repeatedly calling the function you're currently in. For example, until you get to a base case, your function will continue to call itself and return some value.

You can find more information about these terms here.

I liked this table that spells out the differences (you can find its source here):

Property Recursion Interation
Definition Function calls itself. A set of instructions repeatedly executed.
Application For functions. For loops.
Termination Through base case, where there will be no function call. When the termination condition for the iterator ceases to be satisfied.
Usage Used when code size needs to be small, and time complexity is not an issue. Used when time complexity needs to be balanced against an expanded code size.
Code Size Smaller code size Larger Code Size.
Time Complexity Very high(generally exponential) time complexity. Relatively lower time complexity(generally polynomial-logarithmic).

How to Merge Two Lists Iteratively

As discussed above, an iterative approach is one where we'll be looping over some of the code. In the problem of merging lists, we'll want to continue to check the nodes of the list, as long as there are nodes to be checked. I'll first go through the code, and then use an example to illustrate it.

Coding the Iterative Solution

To start this problem, we can create a new list, which we'll be returning at the end of the function. We can do this by creating a new ListNode (a property given to us in the problem), and setting a variable equal to the head of the list.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  //...
}

As long as there are still nodes in both of the inputted lists, we should be comparing their values. Since this is an iterative approach, we'll set up a while loop that keep on executing as long as l1 and l2 are not null.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    //...
  }

  //...
}

An important thing to keep track of while doing iterative solutions is that, at some point, you need to break out of the loop--otherwise, you'll have an infinite loop. That means that inside of the while loop, we have to keep moving forward in both of the inputted lists, so that at some point we get to the end of the list.

Because we're trying to make a sorted list, we'll want to compare the values at the nodes in the list that we're currently on. So, if the value at l1 is less than or equal to the value at l2, we can do something; otherwise, we'll do something else. (Note: it's not necessary for it to be 'less than or equal to'--it would work just as well if we simply said 'less than').

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      //...
    } else {
      //...
    }
  }

  //...
}

In this first case, is the value at l1 is smaller, then we can say that the next node in the list that will be returned will be equal to l1. We can do this by setting current.next equal to l1. We'll also want to keep moving down l1, by setting l1 equal to l1.next. And finally, we'll want to move down the list that will be returned, by setting current equal to current.next.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
      current = current.next;
    } else {
      //...
    }
  }

  //...
}

We can do a similar thing in the 'else' statement. If the value at l2 is smaller, then the next node in the result list will be l2, and we can move down in both l2 and current.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
      current = current.next;
    } else {
      current.next = l2;
      l2 = l2.next;
      current = current.next;
    }
  }

  //...
}

At some point, we'll be getting to the end of one of these lists. If there are still values remaining in l1, but l2 is done being checked, then since l1 is already sorted, we can just add the remainder of l1 to current. Similarly, if there are still values in l2, but l1 is done being checked, we'll add the remainder of l2 to current.

And finally, we can return head.next at the bottom of the function.

function mergeTwoListsIterative(l1, l2) {
  let head = new ListNode();
  let current = head;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
      current = current.next;
    } else {
      current.next = l2;
      l2 = l2.next;
      current = current.next;
    }
  }

  if (l2 === null && l1 !== null) {
    current.next = l1;
  }
  if (l1 === null && l2 !== null) {
    current.next = l2;
  }

  return head.next;
}

Using an Example for the Iterative Solution

Per usual, I like using examples and visuals to explain solutions. For this, I'll use two 2-node lists, where l1 = 1 > 4 and l2 = 2 > 3. When the function starts, we have a new list, as well as the two given lists.

A new list, called 'head', which is empty. L1 is blue, and the first node, 1, is highlighted. L2 is red, and the first node, 2, is highlighted.

Comparing the first nodes of l1 and 12, 1 <= 2, so 1 (from l1) will go to the new list, and we'll move over to the next node in l1.

'Head' has one node, 1, which is blue, signifying it came from L1. L1 is now onto the second node, 4. L2 is still on the first node, 2.

Now, we can compare 4 from l1 and 2 from l2. 4 is not <= 2, so we'll go into the else statement. That means we'll add 2 to the result list, and move over to the next node in l2.

'Head' has two nodes, 1 and 2, and 2 is red, signifying it came from L2. L1 is on the second node, 4, and L2 is on the second node, 3.

No we'll compare 4 from l1 and 3 from l2. 4 is not <= 3, so we'll go into the else statement, and add 3 to the result list. We would move onto the next node in l2, but since there is no next node (it's null), we're done checking l2.

'Head' is now 1 > 2 > 3, and 3 is highlighted red because it came from L2. L1 is still on the node 4, and L2 is done, so none of its nodes are highlighted.

We can't enter the while loop since the conditional statement is no longer true (as l2 is null). Therefore, we can add the remainder of l1 to the result list, and we're done!

'Head' is now complete, at 1 > 2 > 3 > 4. No nodes from either L1 or L2 are highlighted.

How to Merge Two Lists Recursively

Recursively solving this problem would mean repeatedly calling on the function, until we hit some form of a base case. The actual code for the recursive solution is smaller than the iterative solution, but I think it's tricky to wrap your head around a recursive approach. After coding it out in JavaScript, I'll use an example to better explain this approach.

Coding the Recursive Solution

The first thing you'll want to do is set up base cases. Base cases are necessary in recursive solutions because you need to set up a point when the function should stop calling itself.

In this case, we'll want to stop checking the nodes if either l1 or l2 is null. If one of the lists is null, return the other list.

function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) {
    return l2;
  } else if (l2 === null) {
    return l1;
  }
  //...
}

Now, if the value at l1 is less than the value at l2, we'll move onto the next node in l1 by setting it equal to the function, this time passing in the next node from l1, and the same node from l2. Then, we'll return l1. (I know this is super tricky, but hopefully the explanation later will better explain what's going on here.)

function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) {
    return l2;
  } else if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = mergeTwoListsRecursive(l1.next, l2);
    return l1;
  } else {
    //...
  }
}

We'll then do the same if l2 is <= to l1, but this time we'll move to the next node in l2, and recursively call the function by passing in l1 and l2.next. Then, we'll return l2.

function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) {
    return l2;
  } else if (l2 === null) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = mergeTwoListsRecursive(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoListsRecursive(l1, l2.next);
    return l2;
  }
}

Using an Example for the Recursive Solution

While recursive solutions have some benefits, I find them very hard to understand just by looking at the code alone. If you're like me, walking through an example is very helpful.

I'll use the same example as I did in the iterative solution, so l1 = 1 > 4 and l2 = 2 > 3.

We'll start with the function and both l1 and l2. Since l1.val < l2.val (1 < 2), we'll call the function, this time passing is l1.next (4), and the same l2 (2). We also will return l1, 1, though that's not going to be returned until the very end.

The function name is at the top, with L1 and L2 being passed in. L1 is at 1, and L2 is at 2. Then L1.next is set to equal the function, but this time 4 and 2 are passed in. The next node in L1, 4, is highlighted, and the same node in L2, 2, is highlighted. 1 is being returned

Now, since l1.val is not less than l2.val (4 is not < 2), we'll call the function, this time passing in l2.next (3), and the same l1 (4). We also will return l2, 2.

Now L2.next is set to equal the function, but passed in are 4 (from L1) and 3 (which is L2.next). 2 is being returned.

Again, l1.val is not less than l2.val (4 is not < 3), so we'll call the function, this time passing in the same l1 (4), but null for l2, since there are no more nodes in l2. We'll also return 3.

L2.next is set to equal the function, with 4 passed in for L1, and null passed in for L2. L2 is done being checked. 3 is returned.

Since l2 is null, we will return l1, which is 4.

L2 is null, so 4 is returned.

Finally, all of the return statements come together, and we'll return each of these values in order.

Arrows show how each return statement is passed up to the function which just called it.

--

Please let me know if you have any questions or comments about any of what I've discussed!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide