Javascript - Merge two sorted linked lists understanding

Question

I'm trying to figure out why in the following function, at certein point they do mergedTail.next = temp; mergedTail = temp; Instead of to have only mergedTail = temp;:

let merge_sorted = function(head1, head2) {
  // if both lists are empty then merged list is also empty
  // if one of the lists is empty then other is the merged list
  if (!head1) {
      return head2;
  } else if (!head2) {
      return head1;
  }

  let mergedHead = null;
  if (head1.data <= head2.data) {
      mergedHead = head1;
      head1 = head1.next;
  } else {
      mergedHead = head2;
      head2 = head2.next;
  }

  let mergedTail = mergedHead;

  while (head1 && head2) {    
      let temp = null;
      if (head1.data <= head2.data) {
          temp = head1;
          head1 = head1.next;
      } else {
          temp = head2;
          head2 = head2.next;
      }

    mergedTail.next = temp;
    mergedTail = temp;
  }

  if (head1) {
      mergedTail.next = head1;
  } else if (head2) {
      mergedTail.next = head2;
  }

  return mergedHead;
};

Many thanks.

It would help if you clicked edit then [<>] snippet editor and added a working minimal reproducible example — mplungjan
– mplungjan, Commented Feb 6, 2021 at 15:41
The best way to understand this algorithm is to use pen and paper. Draw a rectangle for each node and an arrow for a link. Start with two sorted lists containing two elements elements. — Thomas Sablik
– Thomas Sablik, Commented Feb 6, 2021 at 15:45

Thomas · Accepted Answer · 2021-02-06 15:46:02Z

1

mergedTail always refers to the last element of the merged list. temp is set to the element that should be appended to that list next.

By setting mergedTail.next = temp, the element temp is appended to the merged list. But now mergedTail no longer refers to the last element, but to the second-to-last element. So we assign mergedTail = temp to move it one step ahead, and maintain our invariant.

I would personally have preferred mergedTail = mergedTail.next, which is equivalent and maybe slightly less efficient, but makes the intent clearer.

answered Feb 6, 2021 at 15:46

Thomas

183k57 gold badges383 silver badges510 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Vinni Over a year ago

No sorry, getting again confused. My question was, once you do mergedTail = temp you are overriding the entire mergedTail obj, so even mergedTail.next. This is what I cannot understand.

Thomas Over a year ago

You're not overwriting the entire object, only the reference to that object. Yes, there's no longer an easy way to access the element that mergedTail originally referred to, but you don't need it anymore; you only need the mergedHead to eventually return it from the function.

Collectives™ on Stack Overflow

Javascript - Merge two sorted linked lists understanding

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related