Linked List

In this chapter you will learn the basics of linked list and how to apply it in a different problems.

A linked list is a linear data structure where each element is a separate object. Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that the head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

Problem

Given a linked list, write a function to reverse the list.

Example

// Definition for singly-linked list.
function ListNode(val) {
  this.val = val;
  this.next = null;
}

let head = new ListNode(1);

head.next = new ListNode(2);

head.next.next = new ListNode(3);

head.next.next.next = new ListNode(4);

console.log(reverseList(head)); // 4 -> 3 -> 2 -> 1

Solution

General structure

function reverseList(head) {
  let prev = null;
  let current = head;

  while (current !== null) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  return prev;
}

Complexity Analysis

The time complexity of reversing a linked list is O(n) where n is the number of nodes in the list. The space complexity is O(1) since we are using only a constant amount of space.

Practice

• Middle of the Linked List
• Remove Nth Node From End of List
• Merge Two Sorted Lists