Practice DSA interview questions

Given a linked list, segregate all even-valued nodes and odd-valued nodes. The relative order of the even nodes and the odd nodes should remain the same as in the original list. The even nodes should appear first, followed by the odd nodes. This is similar to the 'Partition List' problem, but the condition is based on the node's value (`val % 2 == 0`) instead of a given `x`.

Given a linked list where every node represents a sorted list and contains a `next` and a `bottom` pointer, flatten the list into a single sorted list. The `next` pointer points to the next list, and the `bottom` pointer points to the next node in the same list. For example, given lists `5->10->19->28`, `7->20->22`, `8->50`, etc., the flattened list should be `5->7->8->10->...`. This is a classic hard problem solved using recursion or a min-heap.

Given a doubly linked list, sort it in O(n log n) time using Merge Sort. This is a variation of the standard Merge Sort for singly linked lists. The presence of the `prev` pointer simplifies some operations, like splitting the list, but requires careful pointer management during the merge step to ensure both `next` and `prev` pointers are correctly updated. The core divide-and-conquer strategy remains the same.

Given a sorted doubly linked list of distinct elements, find all unique triplets `(x, y, z)` such that their sum is equal to a given value `target`. This problem extends the 'Find Pairs with a Given Sum' problem. We can solve it efficiently by fixing one element and then using the two-pointer approach on the rest of the list to find the other two elements.

Given a circular linked list, write a function that counts the number of nodes in the list. This is a basic traversal problem, but it requires a careful termination condition. Unlike a standard linked list where you check for `None`, here you must check if you have returned to the starting node. A `do-while` loop structure is a natural fit for this logic.

Given a `head` of a doubly linked list and a key `x`, delete the first occurrence of `x`. This is a fundamental operation that showcases the main advantage of a doubly linked list: you don't need a 'previous' pointer during traversal because each node already has one. You must handle three cases: deleting the head, deleting the tail, and deleting a node in the middle.

Given a binary tree, convert it into a circular doubly linked list *in-place*. The order of nodes in the DLL must be the same as an in-order traversal of the binary tree. The `left` pointer of a `TreeNode` should be treated as the `prev` pointer and the `right` pointer as the `next` pointer. This is a classic recursion problem that requires careful pointer manipulation to 'stitch' the sub-lists together.

Implement a LIFO (Last-In-First-Out) stack using a doubly linked list as the underlying data structure. The stack should support `push`, `pop`, `top`, `isEmpty`, and `size`. Using a doubly linked list for a stack is slightly overkill (a singly linked list is sufficient), but it's a good exercise in pointer management. The 'top' of the stack can be either the head or the tail of the list, as long as it's consistent.

Given a singly linked list and an integer `N`, find the sum of the last `N` nodes of the list. The challenge is to do this in a single traversal of the linked list. This problem can be solved with a clever two-pointer approach, similar to finding the Nth node from the end. One pointer creates a 'window' of size `N`, and another pointer sums up the values within that window.

You are given the `head` of a linked list. Delete the middle node, and return the `head` of the modified list. The middle node of a list with `n` nodes is the `floor(n / 2)`-th node (0-indexed). This problem is a direct application of the 'slow and fast pointer' technique. The goal is to find the node *just before* the middle node, so you can modify its `next` pointer.

Given two sorted linked lists, `list1` and `list2`, the task is to merge them into a single list in descending (reverse sorted) order. For example, `list1 = 5->10->15` and `list2 = 2->3->20` should result in `20->15->10->5->3->2`. This problem can be solved by first merging the lists in ascending order and then reversing the result, but a more direct approach is also possible.

Given the `head` of a singly linked list, check if the list is sorted in ascending order. This is a fundamental list traversal problem that checks for a basic property. It's often a helper function or a preliminary check in more complex algorithms. You must handle both strictly ascending and non-decreasing sorted lists based on the problem's requirements.

Given a singly linked list and a key (an integer), write a function to count the number of times the key appears in the list. This is a basic traversal problem designed to test your understanding of iterating through a linked list. It is a fundamental operation.

Given a singly linked list and an integer `index`, return the data of the node at the `index`-th position (0-indexed). If the index is invalid (out of bounds), return a specific value like -1. This problem tests basic, 0-indexed traversal and error handling. It's a fundamental skill for all other linked list problems.

Given a linked list and two keys `x` and `y`, swap the nodes in the list. You are *not* given the nodes themselves, just their values. You must find the nodes first. This problem is a test of careful pointer manipulation. You need to find both nodes (`x` and `y`) and their *previous* nodes (`prevX` and `prevY`) to re-wire the `next` pointers correctly. Swapping just the values is much simpler but often not what is asked.

Given a singly linked list, move the last element to the front of the list. For example, `1->2->3->4->5` should become `5->1->2->3->4`. This problem is a simple pointer manipulation exercise. It requires finding both the last node and the *second-to-last* node (the new tail).

Given a linked list and two integers `M` and `N`, traverse the list and for every `M` nodes, delete the next `N` nodes. Continue this process until the end of the list. For example, if `M=2, N=2` and list is `1->2->3->4->5->6->7->8`, the result should be `1->2->5->6`. This problem tests iterative traversal and careful pointer manipulation to 'skip' sections of the list.

Given two linked lists, `l1` and `l2`, merge `l2` into `l1` at alternate positions. The merge should be `l1->l2->l1->l2...`. The original `l1` nodes should be modified. For `l1 = 1->2->3` and `l2 = 4->5->6`, the result should be `1->4->2->5->3->6`. This is a list 'weaving' problem that requires careful pointer management to stitch the lists together.

Given a singly linked list and an integer `k`, find the `(n/k)`-th node, where `n` is the number of nodes in the list. Use integer division (`floor(n/k)`). This problem is a straightforward traversal problem. The main solution is to first find the length `n`, calculate the target index, and then traverse again to find the node. A single-pass solution is also possible but less intuitive.

Given two singly linked lists, `headA` and `headB`, write a function to check if they are identical. Two lists are identical if they have the same number of nodes, and the data in corresponding nodes is the same. This is a basic simultaneous traversal problem.

Given a `head` of a circular linked list and a `key`, delete the first node containing the `key`. You must handle multiple cases: 1) The list is empty. 2) The list has one node. 3) The `head` node is the one to be deleted. 4) The node to be deleted is a middle node. 5) The key is not found. Careful pointer management is required to ensure the list remains circular.

Given the `head` of a singly linked list, convert it into a circular linked list. A singly linked list has a `None` at its tail. A circular linked list has its tail's `next` pointer pointing back to the `head`. This is a simple traversal problem to find the tail and update its pointer.

Given a singly linked list representing a number with the most significant digit at the `head`, add one to the number. This is an alternative to the 'reverse and add' method. A recursive solution is very elegant. It performs a post-order-like traversal, carrying the '1' back up the call stack from the tail to the head.

Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return the modified list. This is the recursive solution to the 'Reverse Nodes in k-Group' problem. It's often considered more concise and elegant than the iterative one, but it has O(n/k) space complexity due to the call stack. The logic is to reverse one group and recursively call the function on the rest of the list.

Given the `head` of a linked list and an integer `n`, return the `n`th node from the end. This is a recursive solution to the classic problem. It uses the function call stack to count from the end. We traverse to the end of the list and then, as the stack unwinds, we increment a counter. When the counter reaches `n`, we've found our node.

Given a circular linked list, apply Merge Sort to sort it in ascending order. This is a complex variation. It requires: 1) A way to split a circular list into two *halves* (which will also be circular). 2) A `merge` function that can merge two *sorted circular* linked lists into a single sorted circular list. The splitting is done with slow/fast pointers, and the merging is standard merge logic with careful handling of the circular `next` pointers.

Given the `head` of a singly linked list, check if it's a palindrome. This is a recursive O(n) time and O(n) space (due to call stack) solution. It's an alternative to the in-place reversal or stack methods. The idea is to use the call stack to simulate a 'backward' traversal. We need a global or class-level pointer to traverse 'forward' while the call stack traverses 'backward'.

Given two singly linked lists, find their intersection node. This is an alternative to the 'two-pointer redirect' method. This method is more "brute force" but easy to understand: 1. Find the lengths of both lists, `lenA` and `lenB`. 2. Calculate the difference, `diff = abs(lenA - lenB)`. 3. Move the pointer of the *longer* list ahead by `diff` steps. 4. Now, both pointers are equidistant from the end. Traverse both pointers one step at a time until they meet. The meeting point is the intersection.

Given a sorted doubly linked list, delete all duplicate nodes. For `1->2->2->3->4->4`, the result should be `1->2->3->4`. This is simpler than the singly linked list version because we have `prev` pointers. We just need to find the node to delete and update its neighbors' pointers. Since it's sorted, duplicates are adjacent.

Given a sorted doubly linked list, delete *all* nodes that have duplicate numbers, leaving only distinct numbers. For `1->2->2->3->4->4->5`, the result should be `1->3->5`. This is the harder version. We must remove all occurrences of any number that appears more than once. A dummy node is essential here to handle the case where the head is a duplicate.