Howardism

Linked lists are a fundamental data structure in computer science. They are often used to represent a sequence of elements, where each element is linked to the next one. In this post, we'll introduce linked lists and explore some algorithm questions related to them.

What is a Linked List?

A linked list is a data structure that comprises a sequence of nodes, where each node contains a data element and a reference (or "link") to the next node in the sequence. The first node in the sequence is known as the "head" of the linked list, and the last node is known as the "tail". Here's a simple example of a linked list:

Head -> Node1 -> Node2 -> Node3 -> Tail

In this example, each node contains a data element (e.g., a number or a string) and a reference to the next node in the sequence. The "head" node contains the first element in the list, and the "tail" node is the last element in the list.

class Node {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

One of the main benefits of linked lists is that they can be easily modified by changing the links between nodes. For example, we can insert a new node into a linked list by creating a new node, setting its reference to the next node, and updating the reference of the previous node to point to the new node. Similarly, we can delete a node from a linked list by updating the reference of the previous node to point to the next node (and optionally freeing the memory used by the deleted node).

Algorithm Questions

Now that we have introduced linked lists, let's explore some algorithm questions related to them. In particular, we'll examine three questions: reversing a linked list, finding the middle node of a linked list, and detecting a cycle in a linked list.

Reversing a Linked List

One common question regarding linked lists is how to reverse a linked list. In other words, given a linked list, how can we reverse the order of its nodes? Here's an example:

Input: Head -> Node1 -> Node2 -> Node3 -> Tail
Output: Tail -> Node3 -> Node2 -> Node1 -> Head

There are several ways to solve this problem, but one common approach is to use a "three-pointer" technique. Here's how it works:

Initialise three pointers: prev (initialised to null), curr (initialised to the head of the linked list), and next (initialised to the second node in the linked list).

While curr is not null, do the following:

Set next to the next node in the linked list.
Set the next reference of curr to prev.
Set prev to curr.
Set curr to next.

Set the head of the linked list to prev.

Here's the JavaScript code that implements this algorithm:

function reverseLinkedList(head) {
  let prev = null
  let curr = head
  while (curr !== null) {
    let next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }
  return prev
}

This algorithm has a time complexity of O(n), where n is the length of the linked list (since we need to visit each node once), and a space complexity of O(1) (since we only need to use a constant amount of extra space).

Finding the Middle Node

Given a linked list, we can find its middle node by using the "slow-fast" pointer technique. The idea is to use two pointers: a "slow" pointer that moves one node at a time, and a "fast" pointer that moves two nodes at a time. When the fast pointer reaches the end of the list (i.e., its next node is null), the slow pointer will be pointing to the middle node (or the node just before the middle node if the length of the list is even). Here's an example:

Input: Head -> Node1 -> Node2 -> Node3 -> Node4 -> Tail
Output: Node3

Here's the JavaScript code that implements this algorithm:

function findMiddleNode(head) {
  let slow = head
  let fast = head
  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
  }
  return slow
}

Detecting a Cycle

Finally, another common question involving linked lists is how to detect whether a linked list contains a cycle (i.e., a loop where a node points to a previous node in the list). Here's an example:

Input: Head -> Node1 -> Node2 -> Node3 -> Node4 -> Node2
Output: true

To detect a cycle in a linked list, we can use the "slow-fast" pointer technique again. We start by initialising two pointers: a "slow" pointer that moves one node at a time, and a "fast" pointer that moves two nodes at a time. If there is a cycle in the list, the fast pointer will eventually "catch up" to the slow pointer (since it is moving twice as fast). If there is no cycle, the fast pointer will reach the end of the list (i.e., its next node is null) and we can return false.

Here's the JavaScript code that implements this algorithm:

function hasCycle(head) {
  let slow = head
  let fast = head
  while (fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) {
      return true
    }
  }
  return false
}