Open in app

Sign in

Write

Sign in

Linked list coding pattern

Dilip Kumar
20 min readSep 20, 2024

--

Floyd’s cycle-finding algorithm

  1. It is used to detect cycles in linked lists.
  2. It works by having two pointers, one moving at a constant speed (the tortoise) and the other moving at twice the speed (the hare).
  3. If there is a cycle in the linked list, the two pointers will eventually meet.

141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true

Approach: Apply cycle detection

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next; 
        if(slow === fast) {
            break;
        }
    }
    return !(!fast || !fast.next);
};

142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/description/

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Approach: Use cycle detection

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let slowPtr = head;
    let fastPtr = head;
    while(fastPtr && fastPtr.next ) {
        slowPtr = slowPtr.next;
        fastPtr = fastPtr.next.next;
        
        // if both are same then break
        if(slowPtr === fastPtr) {
            break;
        }        
    }
    
    // if no cycle
    if(!fastPtr || !fastPtr.next) {
        return null;
    }
    
    // run both pointer as slow pointer until they meet again 
    slowPtr = head;
    while(slowPtr !== fastPtr) {
        slowPtr = slowPtr.next;
        fastPtr = fastPtr.next;
    }
    return slowPtr;
};

876. Middle of the Linked List

https://leetcode.com/problems/middle-of-the-linked-list/description/

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

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

Approach: Apply slow/fast pointer

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

287. Find the Duplicate Number

https://leetcode.com/problems/find-the-duplicate-number/description/

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Approach: Use cycle detection

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let slow = nums[0];
    let fast = nums[0];
    
    while(true) {
        slow = nums[slow];
        fast = nums[nums[fast]];
        if(slow === fast) {
            break;
        }
    }
    
    // reset slow
    slow = nums[0];
    while(slow !== fast) {
        slow  = nums[slow];
        fast = nums[fast];
    }
    return slow;
};

202. Happy Number

https://leetcode.com/problems/happy-number/description/

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true

Approach# Apply cycle detection

const getNext = num => {
    let sum = 0;
    while(num  !== 0) {
        const digit = num % 10;
        sum += digit * digit;
        // update num
        num = Math.floor(num/10);        
    }
    return sum;
}
/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    // Apply flyod's algo to detect the cycle
    let slow = n;
    let fast = n;
    while(fast !== 1 && getNext(fast) !== 1) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));

        // if slow become fast then there is cycle 
        if(slow === fast) {
            return false;
        }        
    }
    return true;
};

148. Sort List

https://leetcode.com/problems/sort-list/description/

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

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

Approach# Apply merge sort

  1. Write function to get middle node using slow/fast pointer approach
  2. As a manager, split into two lists, left and middle
  3. Ask two workers to sort left and right list
  4. Use the two sorted list from worker and let manager to sort it
const getMiddleNode = (head) => {
    let slow = head;
    let fast = head;
    let ans = slow;
    while(slow !== null && fast !== null && fast.next !== null ) {
        ans = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    return ans;
}
const mergeTwoSortedList = (left, right) => {
    const head = new ListNode();
    let node = head;
    while(left && right) {
        if(left.val <= right.val) {
            // Choose left
            node.next = left;
            left = left.next;
        } else {
            // Choose right
            node.next = right;
            right = right.next;
        }
        // Move next ptr
        node = node.next;
    }
    // Copy rest of the list
    node.next = left ? left: right;
    return head.next;
}
const mergeSort = (node) => {
    // Base case
    if(node == null || node.next == null) {
        return node;
    }
     // Find out middle node
     const middle = getMiddleNode(node);
     let left = node;
     let right = middle.next;
     middle.next = null; // Split into two list

     // Let worker to sort left and right list
     left = mergeSort(left);
     right = mergeSort(right);

     // Merge two sorted list
     return mergeTwoSortedList(left, right);
 }
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    return mergeSort(head);
};

206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/description/

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

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

Approach: Recursion

const recursive = node => {
    // if leaf node then return as root
    if(node.next === null) {
        return node;
    }
    const head = recursive(node.next);
    // flip the direction
    const next = node.next;
    next.next = node;
    node.next = null;
    return head;
 }
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(head === null) {
        return head;
    }
    return recursive(head);
};

Approach#2: Iterative

const iterative = head => {
    let node = head;
    let prev = null;
    while(node) {
        const next = node.next;

        // Flip direction
        node.next = prev;

        prev = node;
        node = next;
    }
    return prev;
 }
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(head === null) {
        return head;
    }
    return iterative(head);
};

25. Reverse Nodes in k-Group

https://leetcode.com/problems/reverse-nodes-in-k-group/description

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

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

Approach #1: Recursive

The problem statement mentions that if there are < k nodes left in the linked list, then we don't have to reverse them. This implies that we first need to count k nodes before we get on with our reversal.

This implies at least two traversals of the list overall. One for counting, and the next, for reversals.

We can leverage k to perform the reversal of first k nodes as below using iterative version.

const reverseLinkedList = (head, k) => {
    let new_head = null;
    let ptr = head;
    while (k > 0) {
        const next_node = ptr.next;
        ptr.next = new_head;
        new_head = ptr;
        // move on to the next node
        ptr = next_node;
        k--;
    }
    return new_head;
}

In every recursive call, we first reverse k nodes, then recurse on the rest of the linked list. When recursion returns, we establish the proper connections.

Following is code for reference.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const reverseLinkedList = (head, k) => {
    let new_head = null;
    let ptr = head;
    while (k > 0) {
        const next_node = ptr.next;
        ptr.next = new_head;
        new_head = ptr;
        // move on to the next node
        ptr = next_node;
        k--;
    }
    return new_head;
}
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    let count = 0;
    let ptr = head;

    // first see if there are at least k nodes left in the linked list
    while (count < k && ptr) {
        ptr = ptr.next;
        count++;
    }
    // if we have k nodes left then we can reverse them
    if (count === k) {
        const reverseHead = reverseLinkedList(head, k);
        // Now recruse on remaining
        // before we recurse, rewire the connection
        head.next = reverseKGroup(ptr, k);
        return reverseHead;
    }
    // no need to reverse
    return head;
};

Approach #2: Iterative

The idea here is the same as before except that we won’t be making use of the stack here and rather use a couple additional variables to maintain the proper connections along the way. We still count k nodes at a time. If we find k nodes, then we reverse them.

  1. head ~ which will always point to the original head of the next set of k nodes.
  2. revHead ~ which is basically the tail node of the original set of k nodes. Hence, this becomes the new head after reversal.
  3. ktail ~ is the tail node of the previous set of k nodes after reversal.
  4. newHead ~ acts as the head of the final list that we need to return as the output. Basically, this is the kth node from the beginning of the original list.
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const reverseLinkedList = (head, k) => {
    let new_head = null;
    let ptr = head;
    while (k > 0) {
        const next_node = ptr.next;
        ptr.next = new_head;
        new_head = ptr;
        // move on to the next node
        ptr = next_node;
        k--;
    }
    return new_head;
}
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    let ptr = head;
    let ktail = null;
    let new_head = null;
    while (ptr) {
        let count = 0;

        // Start counting node from new head
        ptr = head;

        // first see if there are at least k nodes left in the linked list
        while (count < k && ptr) {
            ptr = ptr.next;
            count++;
        }
        // if we have k nodes left then we can reverse them
        if (count === k) {
            const reverseHead = reverseLinkedList(head, k);
            // Now recruse on remaining
            // before we recurse, rewire the connection
            // new_head is the head of the final linked_list
            if (!new_head) { // Initialize only once
                new_head = reverseHead;
            }
            // ktail is the tail of the previous block of reversed k nodes
            if (ktail) {
                ktail.next = reverseHead
            }
            ktail = head;
            head = ptr;
        }
    }
    // Attach the final, possibly un-reversed portion
    if(ktail) {
        ktail.next = head;
    }
    return new_head === null? head: new_head;
};

2807. Insert Greatest Common Divisors in Linked List

https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/description

Given the head of a linked list head, in which each node contains an integer value.

Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.

Return the linked list after insertion.

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Example 1:

Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]

Approach: Calculate gcd and insert new node

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const gcd = (a, b) => {
    // a = b*p +c, gcd(a,b) = gcd(b, a%b)
    if (b === 0) {
        return a;
    }
    return gcd(b, a % b);
}
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertGreatestCommonDivisors = function (head) {
    let curr = head;
    while (curr) {
        const next = curr.next;
        if (!next) {
            break;
        }
        const val = gcd(curr.val, next.val);
        const node = new ListNode(val);
    
        curr.next = node;
        node.next = next;
        // reset pointers
        curr = next;
    }
    return head;
};

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/description/

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

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

Approach: Use stack with slow/fast pointer

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    const stack = [];
    // first reach at middle
    let slowPtr = head;
    let fastPtr = head;    
    while(fastPtr && fastPtr.next) {
        stack.push(slowPtr.val);
        slowPtr = slowPtr.next;
        fastPtr = fastPtr.next.next;
    }
    
    // In case of odd
    if(fastPtr) {
        slowPtr = slowPtr.next; 
    }

    // Compare remaining with stack
    while(slowPtr) {
        const top = stack.pop();
        if(top !== slowPtr.val) {
            return false;
        }
        slowPtr = slowPtr.next;
    }
    return stack.length === 0;
};

430. Flatten a Multilevel Doubly Linked List

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Approach 1# DFS with recursion

/**
 * // Definition for a _Node.
 * function _Node(val,prev,next,child) {
 *    this.val = val;
 *    this.prev = prev;
 *    this.next = next;
 *    this.child = child;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var flatten = function (head) {
    if (!head) {
        return head;
    }

    let prev = null;
    const dfs = (node) => {
        const next = node.next;
        const child = node.child;
        node.child = null;
        if (prev) {
            prev.next = node;
        }
        node.prev = prev;
        prev = node;
        for (const neighbor of [child, next]) {
            if (neighbor) {
                dfs(neighbor);
            }
        }
    }
    dfs(head);
    return head;
};

Approach 2# Apply dfs by iterative

/**
 * @param {Node} head
 * @return {Node}
 */
var flatten = function(head) {
    if(!head) {
        return head;
    }
    const stack = [head];
    let prev = null;
    while(stack.length > 0) {
        
        const current = stack.pop();

        // first scan the next
        if(current.next) {
            stack.push(current.next); 
        }
        
        // process child
        if(current.child) {
            stack.push(current.child);  
            current.child = null;
        }
        
        current.prev = prev;
        if(prev) {
            prev.next = current;
        }
        
        prev = current;
    }
    return head;
};

24. Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/description/

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Explanation:

Approach

  1. Traverse two at a time
  2. swap both
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let prev = null;
    let current = head;
    if(!current) {
        return head;
    }
    let next = current.next;
    while(current && next) {
        // swap current and next
        if(!prev) {
            head = next;
        } else {
            prev.next = next;            
        }        
        current.next = next.next;
        next.next = current;

        
        // advance pointer
        prev = current;
        current = current.next;
        if(current) {
            next = current.next;   
        } else {
            next = null;
        }
    }
    return head;
};

19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

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

Example 1:

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

Approach

  1. Get the count of nodes
  2. Get the index of expected node to be deleted.
  3. Handle head deletion separately.
  4. Keep track of prev node and delete the target node
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // first pass to get total nodes
    let total = 0;
    let node = head;
    while(node) {
        total++;
        node = node.next;
    }
    const expectedNodeToRemoved = total - n;
    // if head to be deleted
    if(expectedNodeToRemoved === 0) {
        return head.next;
    }
    // Iterate to find out prev node
    let counter = 0;
    node = head;
    while(counter < expectedNodeToRemoved - 1) {
        counter++;
        node = node.next;
    }
    // delete node
    node.next = node.next.next;
    return head;
};

725. Split Linked List in Parts

https://leetcode.com/problems/split-linked-list-in-parts/description/

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:

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

Approach # Build as we scan

  1. Get the size of the linked list.
  2. split=floor(size/k)
  3. rest=size%k
  4. If k > size then we need to fill upto k .

Following is code for reference.

const findCount = (head) => {
    let node = head;
    let count = 0;
    while (node) {
        count++;
        node = node.next;
    }
    return count;
}
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function (head, k) {
    const size = findCount(head);
    const split = Math.floor(size / k);
    let rest = size % k;
    let counter = 0;
    const ans = [];
    let node = head;
    let local = head;
    let prev = null;
    while (counter < size && node) {
        ans.push(local);
        // Run as per size
        for (let i = 0; i < split && node; i++) {
            prev = node;
            node = node.next;
            counter++;
        }
        // Check if needs to add extra
        if (rest > 0 && node) {
            prev = node;
            node = node.next;
            counter++;
            rest--;
        }
        // break node 
        prev.next = null;
        local = node;
    }
    // Add rest
    while (counter < Math.max(size, k)) {
        ans.push(null);
        counter++;
    }
    return ans;
};

Approach#2: Build as per k size

We can also write code as below.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const findCount = (head) => {
    let node = head;
    let count = 0;
    while (node) {
        count++;
        node = node.next;
    }
    return count;
}
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function (head, k) {
    const size = findCount(head);
    const split = Math.floor(size / k);
    let rest = size % k;

    const ans = [];
    let node = head;
    let prev = null;
    for (let i = 0; i < k; i++) {
        ans.push(node);
        let currentSize = split;
        if (rest > 0) {
            currentSize++;
            rest--;
        }
        // Skip linked list
        for (let j = 0; j < currentSize; j++) {
            prev = node;
            node = node.next;
        }
        // break the list
        if (prev) {
            prev.next = null;
        }
    }
    return ans;
};

83. Remove Duplicates from Sorted List

https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/

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.

Example 1:

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

Approach# Compare current node with next to find duplicate

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let node = head;
    while (node && node.next) {
        if (node.val === node.next.val) {
            node.next = node.next.next;
        } else {
            node = node.next;
        }
    }
    return head;
};

82. Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

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

Approach #1: First get the duplicates then delete these in second pass

  1. Let’s start from the most challenging situation: the list head is to be removed.
  2. The standard way to handle this use case is to use the so-called Sentinel Node.
  3. Sentinel nodes are widely used for trees and linked lists such as pseudo-heads, pseudo-tails, etc.
  4. They are purely functional and usually don’t hold any data. Their primary purpose is to standardize the situation to avoid edge case handling.

Following is code for reference.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    const sentinel = new ListNode(-1001, head);
    // pass 1: Get the list of target targets
    let node = head;
    let prev = sentinel;
    const target = new Set();
    while (node) {
        // if same as next then target for deleting
        if (node.val === prev.val) {
            target.add(node.val);
        }
        prev = node;
        node = node.next;
    }
    // pass 2: delete the targets
    node = head;
    prev = sentinel;
    while (node) {
        if (target.has(node.val)) {
            prev.next = node.next;
        } else {
            prev = node;
        }
        node = node.next;
    }
    return sentinel.next;
};

Approach #2: Single pass

  1. Instead of comparing current node with previous node, we can compare current node with next node.
  2. This way we can preserve prev node to store predecessor only.
  3. Every time we find current node is same as next node, we can start a separate loop to skip all the duplicates nodes.
  4. At the end, use predecessor node to update the next pointer to skip the last leftover duplicate node

Following is code for reference.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    const sentinel = new ListNode(0, head);
    let pred = sentinel;
    let node = head;
    while(node) {
        // Check for duplicates
        if(node.next && node.val === node.next.val) {
            // Skip pointer to the last duplicate node
            while(node.next && node.val === node.next.val) {
                node = node.next;
            }
            // Update predecessor pointer to next to delete all duplicates
            pred.next = node.next;
            // No need to update predecessor here
        } else {
            // No duplicate so keep updating the predecessor
            pred = node
        }
        // move forward
        node = node.next;
    }
    return sentinel.next;
};

146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Approach: Use doubly linked list with head and tail as sentinel nodes

  1. We can use doubly linked list to represent the cache.
  2. On accessing key, we will delete the existing node if exist and add it in end.
  3. To delete at O(1) , we will maintain HashMap <key, node> for quick access.
  4. During put operation, if it exceeds the capacity then remove the first element.
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}
/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    // Use doubly linked list with head and tail pointers
    this.capacity = capacity;
    this.head = new Node(-1, -1);
    this.tail = new Node(-1, -1);
    this.map = new Map();
    this.head.next = this.tail;
    this.tail.prev = this.head;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (!this.map.has(key)) {
        return -1;
    }
    const node = this.map.get(key);
    this.remove(node);
    this.add(node);
    return node.value;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    // if node already exist then first remove then append at the end
    if (this.map.has(key)) {
        const oldNode = this.map.get(key);
        this.remove(oldNode);
    }
    // Create node
    const node = new Node(key, value);
    this.map.set(key, node); // update map
    this.add(node);

    // if size is more than capacity then remove the first
    if (this.map.size > this.capacity) {
        const first = this.head.next;
        this.remove(first);
        this.map.delete(first.key);
    }

};
LRUCache.prototype.add = function (node) {
    // Add at the end
    const prevEnd = this.tail.prev;
    prevEnd.next = node;
    node.prev = prevEnd;
    node.next = this.tail;
    this.tail.prev = node;
}

LRUCache.prototype.remove = function (node) {
    // Only remove link for prev and next node is enough. 
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

Happy coding!!!

Data Structure Algorithm

--

--

Dilip Kumar
Dilip Kumar

Written by Dilip Kumar

492 Followers
29 Following

With 18+ years of experience as a software engineer. Enjoy teaching, writing, leading team. Last 4+ years, working at Google as a backend Software Engineer.

No responses yet

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams