Practice DSA interview questions

You are given two non-empty linked lists representing non-negative integers. The digits are stored in forward order (most significant digit first). Add the two numbers and return the sum as a linked list in the same format. For `(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)`, you must return `7 -> 8 -> 0 -> 7`. This problem is tricky because you need to add from the 'end' (tail) of the lists, but you only have `next` pointers.

Given the `head` of a singly linked list, return the middle node of the linked list. If there are two middle nodes (in the case of an even number of nodes), return the second middle node. This is a foundational problem that is a sub-problem for many other list operations, such as 'Reorder List' and 'Palindrome Linked List'. The most efficient solution uses the 'Tortoise and Hare' (slow and fast pointer) technique. This allows finding the middle in a single pass with O(1) space complexity, which is a key concept.

Given the `head` of a linked list and two integers `left` and `right` (where `left <= right`), reverse the nodes of the list from position `left` to position `right`, and return the reversed list. This is a common and practical variation of the standard reversal problem. It tests your ability to handle pointers at the boundaries and 'stitch' a sub-list back into the main list. You must carefully track the node *before* the sub-list and the node *after*.

Given the `head` of a linked list and a value `x`, partition it such that all nodes less than `x` come before nodes greater than or equal to `x`. You should preserve the original relative order of the nodes in each of the two partitions. This is a very common interview question. The most straightforward approach is to build two separate linked lists: one for the 'less than' nodes and one for the 'greater than or equal' nodes.

Given the `head` of a linked list and an integer `val`, remove all nodes of the linked list that have `Node.val == val`, and return the new head. This problem is a good test of handling pointer manipulation, especially the edge case where the `head` node itself needs to be removed (or multiple nodes at the start need to be removed). A sentinel or 'dummy' node makes this much easier.

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 1. The parts should be in order. This problem is about calculating the size of each part. The first `n % k` parts will have one extra node.

You are given a singly linked list that represents a non-negative integer. The most significant digit is at the `head`. Add one to this integer. For example, `1->2->3` (123) becomes `1->2->4` (124), and `9->9->9` (999) becomes `1->0->0->0` (1000). The challenge is that the 'carry' propagates from right to left (tail to head), but we only have `next` pointers.

Given the `head` of a linked list, return the list after sorting it in ascending order. The most common follow-up is to do this in O(n log n) time and O(1) space (excluding the recursive call stack). Merge Sort is the ideal algorithm for this. It involves splitting the list in the middle, recursively sorting each half, and then merging the two sorted halves.

Given the `head` of a linked list, sort the list using insertion sort, and return the sorted list's head. Insertion sort is an O(n^2) algorithm. In the context of a linked list, it works by maintaining a 'sorted' sub-list. We iterate through the original list, picking one node at a time (`current`) and finding its correct position in the 'sorted' sub-list, then inserting it there.

You are given the `head` of a linked list. For each node, find the value of the next greater node. That is, for `node[i]`, find the value of `node[j]` such that `j > i`, `node[j].val > node[i].val`, and `j` is the smallest possible index. If it does not exist, the answer is 0. This problem is a combination of linked lists and the monotonic stack pattern.

Given `head` of a singly linked list where each node contains a `0` or `1`. The list holds the binary representation of a number. Return the decimal value of the number. For example, `1->0->1` is `(1 * 2^2) + (0 * 2^1) + (1 * 2^0) = 5`. This can be solved by traversing the list, but the most efficient way involves bit manipulation.

Design a data structure that supports `addAtHead`, `addAtTail`, `addAtIndex`, `deleteAtIndex`, and `get`. This is a foundational design problem. A doubly linked list is different from a singly linked list in that each node also contains a `prev` pointer, pointing to the previous node. This allows for O(1) insertion/deletion *if* you have a reference to the node, and makes some operations (like `addAtTail`) more efficient.

You are given the `head` of a linked list, and an integer `k`. Return the head of the list after swapping the values of the `k`th node from the beginning (1-indexed) and the `k`th node from the end. This problem is a test of pointer manipulation and finding specific nodes. A single pass is possible by finding the *k*-th node, and then using a two-pointer gap to find the *k*-th-from-end node.

Given the `head` of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences. Return the final head of the linked list. This is a challenging problem that can be solved by iterating through the list and using a hash map to store prefix sums. If we see a prefix sum that we've seen *before*, it means the sub-list between those two points sums to zero.

Design a data structure that follows a Least Recently Used (LRU) cache eviction policy. It must support `get(key)` and `put(key, value)`. `get` should return the value or -1. `put` should insert or update the value. When the cache is full, a `put` must evict the *least recently used* item. This is a very common design question. The optimal solution uses a **Hash Map** (for O(1) get) and a **Doubly Linked List** (for O(1) insertion/deletion of the LRU node).

Design a data structure that follows a Least Frequently Used (LFU) cache eviction policy. It must support `get(key)` and `put(key, value)`. When the cache is full, a `put` must evict the *least frequently used* item. If there is a tie, the *least recently used* item is evicted. This is an advanced design problem. A common solution uses two hash maps: one for `key -> Node` and one for `frequency -> DoublyLinkedList` of nodes with that frequency.

Given a linked list, determine if it is circular. A linked list is circular if at some point, a node's `next` pointer points back to a previous node in the list. This is a synonym for 'Linked List Cycle Detection'. The standard 'Floyd's Tortoise and Hare' algorithm is the most efficient way to detect this, using two pointers. A circular list doesn't have a `None` at the end.

Given a `head` of a circular sorted linked list, insert a new element `insertVal` into the list so that it remains a circular sorted list. If the list is empty, create a new circular list. The given node can be *any* node in the list, not necessarily the smallest. This problem is all about handling edge cases: an empty list, a list with one node, and the 'wraparound' case (where `prev.val > curr.val`).

Given a circular linked list, split it into two circular linked lists. If the original list has `n` nodes, the first list should have `ceil(n/2)` nodes and the second should have `floor(n/2)` nodes. This problem can be solved using the 'slow and fast pointer' technique to find the middle (and the node just before the middle) of the list.

Given the `head` of a singly linked list, return `true` if it is a palindrome. This is an alternative solution to the O(1) space, in-place reversal method. This approach uses O(n) space, which is simpler to implement. It involves pushing the first half of the list's values onto a stack and then comparing them against the second half of the list.

Construct a deep copy of a linked list with `next` and `random` pointers. This is an alternative solution to the O(n) space (hash map) method. This clever O(n) time, O(1) space solution involves 'weaving' the new, copied nodes into the original list, then setting the random pointers, and finally un-weaving the lists.

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. Return this repeated number. You must solve the problem without modifying the array and using constant extra space. This problem can be cleverly mapped to a 'Linked List Cycle Detection' problem. Each index `i` can be thought of as a node, and the value `nums[i]` as the 'next' pointer. Since there's a duplicate, a cycle is guaranteed to form.

Given the `head` of a linked list, write a function to remove duplicate nodes from the list. The list is not sorted. For example, if the list is `12->11->12->21->41->43->21`, the output should be `12->11->21->41->43`. This is a common problem that tests the use of an auxiliary data structure, typically a hash set, to keep track of the values you have already seen while traversing the list. An O(n^2) solution without extra space is possible but less efficient.

Given a linked list that contains a cycle, the task is to find the length of the cycle. This is a direct follow-up to the cycle detection problem. Once you find the meeting point of the slow and fast pointers using Floyd's algorithm, you can use that meeting point to traverse the cycle once more to count its length. This demonstrates a deeper understanding of the cycle detection algorithm's properties.

You are given a `node` from a singly linked list to be deleted. You are not given access to the `head` of the list. The given `node` will not be the `tail` node. This is a classic trick question. Since you cannot access the previous node to modify its `next` pointer, the solution is to *not* delete the given node itself, but rather to copy the data from the *next* node into the given node and then delete the next node.

Given two lists sorted in increasing order, create a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed. For example, if the first list is `1->2->3->4->6` and the second is `2->4->6->8`, then the intersection list is `2->4->6`. This problem can be solved efficiently with a two-pointer approach, similar to merging.

Given the `head` of a doubly linked list, reverse the list and return the new head. Reversing a doubly linked list is slightly different from a singly linked list because you have to manage both `next` and `prev` pointers. The core idea is to traverse the list and, for each node, swap its `prev` and `next` pointers. The logic is generally simpler than singly-linked reversal as you don't need a third temporary pointer for the next node.

Design a circular linked list. This data structure is a variation of a standard linked list where the `next` pointer of the last node points back to the `head` instead of being `None`. This creates a closed loop. Your implementation should support basic operations like insertion at the beginning, insertion at the end, and traversal. Handling the circular nature and the `head`/`tail` pointers correctly is the main challenge.

Given a sorted doubly linked list of distinct elements, find all pairs `(x, y)` such that their sum is equal to a given value `target`. This is a linked list version of the classic 'Two Sum' problem. Since the list is sorted and doubly linked, we can use a two-pointer approach that is very efficient, taking O(n) time and O(1) space. The `prev` pointers are key to moving the 'right' pointer backwards.

Given a singly linked list, remove all nodes which have a greater value on their right side. For example, in the list `12->15->10->11->5->6->2->3`, the output should be `15->11->6->3`. This is because for 12, 15 is greater; for 10, 11 is greater; for 5, 6 is greater; and for 2, 3 is greater. The problem can be solved by reversing the list, which simplifies the logic.