Forem: Veronika Fatikhova

Reverse Linked List

Veronika Fatikhova — Fri, 15 Apr 2022 16:25:56 +0000

Let’s practice reversing a singly linked list as this is a popular interview question!

The problem is, given the head of a singly linked list, reverse it, and return the reversed list.

We can solve this problem by reordering the original list instead of creating a new one, and returning the tail node as the new head of the list.

If we’ll look at the first node, what do we know about it? We know that it has a pointer to the next node, and no nodes pointing to it. If we reverse its next pointer backwards immediately, we’ll orphan the rest of the list. In addition, we don't know which node should it point to. We need some helper cursors to keep track of the nodes!

Thus, we will define three cursors: curr to remember the current node, prev to remember its previous node (firstly initialized to null), and tmp to remember the next node (we’ll define it as a local variable inside the loop).

const reverseList = (head) => {
  let curr = head; //cursor to the current node
  let prev = null; //cursor to the previous node
...
}

Since we remember the next node, we can safely change the cursors. But the order is important!

First, we move our curr pointer backwards to link it with the previous node (or null initially):

curr.next = prev;

Then prev becomes our current node, and the current becomes the next node:

prev = curr;
curr = tmp;

That’s it, in the next iteration we can move to the next node and repeat the process.

We keep moving along the list unless we reach the end (the current cursor points to null). By the end of the cycle, we return a new head of the list, our prev node (not prev.next since prev.next is null).

while (curr) { //curr !== null
    let tmp = curr.next; //move cursor to the next node

    curr.next = prev; //1.change curr pointer backwards
    prev = curr; //2.change prev cursor to current
    curr = tmp; //3.move cur cursor to the next node
  }

Let's put it all together.

const reverseList = (head) => {
  let curr = head; //cursor to the current node
  let prev = null; //cursor to the previous node

  while (curr) { //curr !== null
    let tmp = curr.next; //move cursor to the next node

    curr.next = prev; //1.change curr pointer backwards
    prev = curr; //2.change prev cursor to current
    curr = tmp; //3.move cur cursor to the next node
  }
  return prev; //return a new head of the list
};

We can do it better with recursion! Know how? Please feel free to share your solution in the comments!

The Linked List: ADD TWO NUMBERS

Veronika Fatikhova — Thu, 14 Apr 2022 18:24:59 +0000

By this post, I’d like to start a series of Leetcode problems on Linked Lists, one of the common interview questions. Today, we’ll be walking through the Add Two Numbers Problem.

The problem is, given two non-empty linked lists representing two integers where digits are stored in reverse order, add their digits and return the sum as a linked list.

To solve this problem, we are going to use the column method from elementary Math: going through the lists from the head, digits-by-digits sum numbers until we reach the end of both lists: list1 AND list2 (because they may have different lengths).

The first thing we are going to do here is to create a new list since we have to return it at the end.

Using the provided function definition, we create the very first node, with a value equal to 0 by default. That will be the head of our list called list (we always need to remember the very first node to return the whole chain). Actually, we will return the list starting from the next node to skip this first 0.

We also need the second cursor currentNode for pointing to the current node we are working on within the current iteration. Initially, it’s equal to the list’s head but then we will use it to iterate over the list manually.

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head
...

  return list.next; //return head's next node (to skip the first 0)
};

Then we need to initialize two additional variables: sum which will hold the sum of two digits, and carry which will hold the digit “carried over” the next iteration in case the sum of two digits will be >= 10.

...
  let sum = 0;
  let carry = 0;
...

};

Next, we are going to iterate over two lists and sum up their values. We will use the while loop here to run the code unless we reach the end of either of the lists. We also need to think about the case if we still have the carry reminder left by the end of the cycle, so this will be the third condition to check.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
...
}

Within the loop, we will have two if statements in case the lists have different lengths. The pseudocode for the iteration for each list is following:

Check if the current list node still exists (not equal to null).
Add its value to the sum.
Move the pointer cursor to the next node.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }
...
}

By the end of one iteration, we have the sum value.

Now it’s time to check if it is >= 10. If it is (for example, the sum is 12), we will take only the second digit 2, and the first one 1 will be carried over the next iteration.

To split this number into two digits, we’ll use Math division and modulo operation:

while (list1 || list2 || sum > 0) {
...
    carry = Math.floor(sum / 10);
    sum = sum % 10;
...
}

Now we can add a new node to the output list and give it the value of the sum.

Again, by pushing a new node to the end of the list, we are: (1) allocating memory for it, (2) linking it with the current node, (3) initializing its value, and (4) setting up its pointer to null by default.

while (list1 || list2 || sum > 0) {
...
//add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);
...
}

And one more thing we need to do here is to advance the currentNode cursor to the new node we just added for the next iteration.

while (list1 || list2 || sum > 0) {
...
   //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

  //move the cursor to the new node
    currentNode = currentNode.next;
...
}

Lastly, we need to initialize the sum to the carrier before the next iteration (since we’ll add the carrier to the sum in the next round) and reset the sum.

while (list1 || list2 || sum > 0) {
...
    sum = carry;
    carry = 0;
}

Let's put all together:

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head

  let sum = 0;
  let carry = 0;

  while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }

    carry = Math.floor(sum / 10);
    sum = sum % 10;

    //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

    //move the cursor to the new node
    currentNode = currentNode.next;

    sum = carry;
    carry = 0;
  }

  return list.next; //return head's next node (to skip the first 0)
};

We're done!

What about complexity?

Time Complexity of this approach is O(n) where n is the maximum number of nodes of the longest list since we have to traverse the lists.
Space Complexity: O(n) where n is the maximum number of nodes of the longest list since we create a new list in the memory.

Next time, we’ll discuss two more advanced problems:
ADD TWO NUMBERS II
ADD TWO NUMBERS WITH METHODS

I hope this helped! Please let me know if you have additional comments or questions!

The Linked List in JavaScript: implementation, operations (basics)

Veronika Fatikhova — Wed, 13 Apr 2022 23:01:12 +0000

Linked List is a linear data structure, very similar to an array. However, in an array, data is stored as consecutive chunks of values where each element has a particular index. In a linked list, all elements are stored in different memory locations and linked together by pointers (which is the next node’s memory address).

Each element (called a node), contains two parts: data of any type and a pointer to the next element. The last node points to null (in human language, nothing). The reference to the very first element is commonly called head, and the reference to the last element is called tail. We don’t always need to know the tail but must remember the first element of the list.

In this article, we’ll take a look at the basics: implementation of a singly linked list in JavaScript and some operations on it.

Implementation of a linked list in JS

In programming languages, a linked list can be represented either as a separate data structure or just as a reference to the list's head that is more commonly used in interview questions. Having the head, a cursor to the very first node, we can refer to the whole list because, again, all its nodes in the computer memory are linked together.

In JavaScript, we can implement a singly-linked list with a class or with a function. In both cases, we have to define two parts: data and a pointer to the next node.

That’s how we can define it with a class of linked lists:

class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

That’s how we can define it with function:

const ListNode = (val, next) => {
  this.val = (val===undefined ? 0 : val);
  this.next = (next===undefined ? null : next);
}

Note that with the last implementation, if we don’t pass the arguments the node will be created with 0 value and null pointer by default.

Let’s create the first node instance with a value of 1 and set up the head cursor.

let node1 = new ListNode(1);
let head = node1;

We created a list containing one single node. Setting the head cursor, we can further return the whole list head=[1]:

return head;

Operations on a linked list

Now, let’s implement some basic operations on a singly linked list, such as: inserting a node, deleting the node, and traversing the list.

Inserting a node

The simplest operation on the list could be appending a node (adding to the end of a list). To do so we just have to allocate memory for a node and link it with the previous node:

node1.next = new ListNode(2);

We added the second node to our list: head=[1,2].

At the same time, to prepend a node (push at the beginning of the list), we firstly create a node and then change pointers so that the new node first links to the rest of the list, and then the head points to our new node (we know that the initial list is not empty):

const pushFront = (head) => {
  let newNode = new ListNode(0);
  newNode.next = head;
  head = newNode;
  return head;
};

We returned our new list head=[0,1,2].

Prepending a node can be made in constant O(1) time while to append to the last node we have to traverse the list till the last node is found. This can be made in linear O(n) time when n is the length of the list.

Deleting a node

To delete a node we can use a simple approach of mutating the nodes where we just change the values of a node we’re going to delete to its next node’s values (you can find a similar Leetcode problem here):

const deleteNode = (node) => {
  node.val = node.next.val;
  node.next = node.next.next;
}

Here we don’t return anything as we just changed the values in place.

Traversing the list

In a singly linked list, we can move only in one direction, forward. To traverse through the list, we should define an additional pointer to keep track of the current node we’re working on. We have to start from the head and keep following the next pointers until we reach the null pointer.

For each iteration, we check if the current node exists (not equal to null). When we reach the null, we reach the end of the list:

let curNode = head;
  while (curNode) {
    curNode = curNode.next;
  }

Similarly, getting the last element can be implement as follows (we know that the list is not empty):

const getLast = (head) => {
  let curNode = head;
  while (curNode) {
    curNode = curNode.next;
  }
  return curNode;
};

Now we can traverse the list with one additional pointer. In the next articles, I’ll show you how we can search an element in the list faster and more efficiently, using the two-pointers approach.

I hope this article helped you to understand the basics of a singly linked list.