Implementing a Linked List

When storing multiple elements, we typically use arrays. But arrays have a drawback: slow insertion and deletion. Since arrays use contiguous memory — which enables random access with O(1) read efficiency — insertions and deletions are complex, with an average time complexity of O(n).

Linked lists are different: elements in a linked list are not stored contiguously in memory. Each element consists of a node that stores the element itself and a reference (pointer) to the next element. As shown in the diagram:

Let's implement it in code:

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

Linked List Algorithm Problems

Now that we've implemented the linked list data structure, let's solve a few linked list problems:

Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Input: head = [1,1,2]
Output: [1,2]

This is considered easy on LeetCode. If you can understand the problem, you can solve it:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if (!head) {
        return head;
    }
    let cur = head;
    // Iterate through the next element of the current node
    while (cur.next) {
      // If the next element has the same value as current, skip it by pointing to the one after
        if (cur.val === cur.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return head;
 };

Time complexity: O(n)
Space complexity: O(1)

Merge Two Sorted Lists

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.

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

There are two approaches to this problem. Let's start with the recursive solution:

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if(l1 === null){  // If l1 is null, return l2
        return l2
    }else if(l2 === null){    // If l2 is null, return l1
        return l1
    }else if(l1.val < l2.val){    // If l1 < l2, recurse with l1.next and l2
        l1.next = mergeTwoLists(l1.next, l2);
        return l1
    }else{
        // If l2 <= l1, recurse with l1 and l2.next
        l2.next = mergeTwoLists(l1, l2.next);
        return l2
    }
};

The recursive version is fairly easy to understand — most people can follow the code. The second approach is slightly harder to grasp. It uses iteration with a sentinel node (prehead), which makes it easier to return the merged list at the end.

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
  // Sentinel node
  const prehead = new ListNode(-1);

  let prev = prehead;
  // Iterate
  while (l1 != null && l2 != null) {
      if (l1.val <= l2.val) {
          prev.next = l1;
          l1 = l1.next;
      } else {
          prev.next = l2;
          l2 = l2.next;
      }
      prev = prev.next;
  }

  // At most one of l1 and l2 is non-null at this point, so connect it to the end
  prev.next = l1 === null ? l2 : l1;

  return prehead.next;
};

Time complexity: O(m + n), where m and n are the lengths of the two lists.
Space complexity: O(1).

Remove Nth Node From End of List

This problem is rated Medium on LeetCode:

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Follow up: Could you do this in one pass?

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Algorithm code:

var removeNthFromEnd = function(head, n) {

  // Helper function to get linked list length
  function getLength(head){
      let length = 0;
      while(head){
          length++;
          head = head.next;
      }
      return length;
  }

  // Create a dummy node whose next is head
  const dummy = new ListNode(0, head);

  const length = getLength(head);

  // Traverse (length - n) times to reach the node before the one to delete
  let current = dummy;
  for(let i = 0; i < length - n ; i++){
      current =  current.next;
  }
  // Delete the node by skipping it
  current.next = current.next.next;
  return dummy.next;
};

This might be a bit hard to follow. LeetCode's official explanation is very clear. Here's the diagram:

dummy is current, and length - n equals 2, so current is the node with value 2. Simply change the next pointer to skip the target node.

Time complexity: O(n), where n is the length of the list.
Space complexity: O(1).