Merge 2 Sorted Linked List with Javascript - Function Help

1

Hello my question will be about data structures in javascript. I try to solve a problem on hackerrank with javascript. merge-two-sorted-list-problem

I can solve that by writing this code

function mergeLists(head1, head2) {
  let headNode = {
    data: 0,
    next: null
  }

  let tail = headNode;
  let node1 = head1;
  let node2 = head2;


  while (true) {
    if (!node1) { tail.next = node2; break; }
    if (!node2) { tail.next = node1; break; }

    if (node1.data <= node2.data) {
      let temp = node1;
      if (!temp) return;

      node1 = node1.next;
      temp.next = tail.next;
      tail.next = temp;
    } else {
      let temp = node2;
      if (!temp) return;

      node2 = node2.next;
      temp.next = tail.next;
      tail.next = temp;
    }

    tail = tail.next;
  }

  return headNode.next;
}
// src -> source node reference
// dest -> tail reference
function moveNode(node, tail) {

  let temp = node; // temp taşınacak node
  if (!temp) return;

  node = node.next;
  temp.next = tail.next;
  tail.next = temp;
}

But when I trying to structure my code better, I try to write function named addNode I am getting unexpected behaviour in my code. When I write this code:

const SinglyLinkedListNode = class {
  constructor(nodeData) {
    this.data = nodeData;
    this.next = null;
  }
};

function mergeLists(head1, head2) {
  let headNode = new SinglyLinkedListNode(0);

  let tail = headNode;
  let node1 = head1;
  let node2 = head2;


  while (true) {
    if (!node1) { tail.next = node2; break; }
    if (!node2) { tail.next = node1; break; }

    if (node1.data <= node2.data) {
      addNode(node1, tail);
    } else {
      addNode(node2, tail);
    }

    tail = tail.next;
  }

  return headNode.next;
}
// node -> source node reference
// tail -> tail reference
function addNode(node, tail) {
  let temp = node; // the moving node
  if (!temp) return;

  node = node.next;
  temp.next = tail.next;
  tail.next = temp;
}

As you can see in the if blocks I simply call the function and add to reference node to that function. When I debug my code node variable refers to this:

debug sc
debug sc1512×1350 351 KB

After the function finished I expect that node1 variable = node variable inside that function.

debug sc2
debug sc21884×1318 371 KB

I looked at pass by reference and pass by value topics but I do not understan how javascript do this behind the since. And I am really want to imporve myself at data structures with javascript.

All help is really appreciated.

Thank you.

Furkan

2

Hey @afozbek, here’s my review:

function mergeLists(head1, head2) {
  let headNode = {
    // unnecessary properties, just headNode = {} should be enough
    data: 0,
    next: null
  }

  let tail = headNode;
  let node1 = head1;
  let node2 = head2;


  while (true) {
    // can be substituted with OR operator:
    // if (!node1 || !node2) { tail.next = node1 || node2; break; }
    if (!node1) { tail.next = node2; break; }
    if (!node2) { tail.next = node1; break; }

    if (node1.data <= node2.data) {
      // unnecessary temp variable and check after
      let temp = node1;
      if (!temp) return;

      /** All you need is to assign tail next to min node and make step forward with the node:
      node1 = node1.next;
      temp.next = tail.next;
      tail.next = temp;
      */
      tail.next = node1;
      node1 = node1.next;
    } else {
      // Do the same for else
      let temp = node2;
      if (!temp) return;

      node2 = node2.next;
      temp.next = tail.next;
      tail.next = temp;
    }

    tail = tail.next;
  }

  // Congrats ;)
  return headNode.next;
}
1 Like
3

You are exactly right. Code can be improved. I just don’t understand how I can’t do exactly same thing when implementing the function :frowning:

4

It wasn’t hard for me as you’ve done most of the work. You can try same approach when you put your code aside for a night and try to review it the next morning with fresh eyes.

Other technique that always works, write steps on paper/whiteboard before coding

1 Like