Practice — Linked Lists (6 questions)

Given the head of a singly linked list, reverse the list in place and return the new head. You may not allocate a new list of nodes — you must rewire the existing next pointers.

A singly linked list node looks like this:

Node
+------+------+
| val  | next |---> (next node or None)
+------+------+

Example 1

Input:  1 -> 2 -> 3 -> 4 -> 5 -> None
Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

Example 2

Input:  1 -> 2 -> None
Output: 2 -> 1 -> None

Example 3

Input:  None
Output: None

Constraints

• The number of nodes is in the range [0, 5000].
• -10^5 <= Node.val <= 10^5.
• Solve it iteratively in O(1) extra space (a recursive O(n)-space solution is also acceptable as a follow-up discussion).

Given the head of a singly linked list and an integer k, remove the k-th node counting from the end of the list (the last node is k = 1), and return the head of the resulting list. Do this in a single pass through the list.

Example 1

Input:  1 -> 2 -> 3 -> 4 -> 5 -> None, k = 2
Output: 1 -> 2 -> 3 -> 5 -> None
(the 2nd-from-last node, 4, is removed)

Example 2

Input:  1 -> None, k = 1
Output: None

Example 3

Input:  1 -> 2 -> None, k = 2
Output: 2 -> None
(removing the head)

Constraints

• The number of nodes is n, with 1 <= n <= 10^5.
• 1 <= k <= n (k is always valid for the given list).
• Aim for O(n) time using a single pass and O(1) extra space.

You are given the heads of two singly linked lists, headA and headB. The two lists may converge into a shared tail (i.e., after some point, the same physical nodes are shared by both lists), or they may not intersect at all. Return the node at which the two lists intersect, or None if they do not intersect. Intersection is defined by node identity (the same node object), not by equal values.

A:  a1 -> a2
              \
                c1 -> c2 -> c3 -> None
              /
B:  b1 -> b2 -> b3

Here headA and headB intersect at node c1.

Example 1

A: 4 -> 1 -\
             8 -> 4 -> 5 -> None
B:      5 -> 6 -> 1 -/
Output: node with value 8 (the intersection node)

Example 2

A: 1 -> 2 -> None
B: 3 -> 4 -> None
Output: None (no intersection)

Constraints

• Combined node count across both lists is at most 3 * 10^4.
• The lists themselves are guaranteed to be acyclic (no cycles).
• Aim for O(n + m) time and O(1) extra space — do not use extra data structures like a hash set of visited nodes.

Design a data structure for a Least Recently Used (LRU) cache that supports the following operations, both in O(1) average time:

• get(key): return the value associated with key if it exists in the cache, otherwise return -1. Accessing a key counts as using it, so it becomes the most recently used entry.
• put(key, value): insert or update the value for key. If inserting a new key would exceed the cache's fixed capacity, evict the least recently used entry first. Inserting or updating a key also counts as using it.

Example

cache = LRUCache(capacity=2)
cache.put(1, 1)          # cache: {1=1}
cache.put(2, 2)          # cache: {1=1, 2=2}
cache.get(1)              # returns 1, cache order (MRU->LRU): 1, 2
cache.put(3, 3)          # evicts key 2 (LRU), cache: {1=1, 3=3}
cache.get(2)              # returns -1 (not found)
cache.put(4, 4)          # evicts key 1 (LRU), cache: {3=3, 4=4}
cache.get(1)              # returns -1 (not found)
cache.get(3)              # returns 3
cache.get(4)              # returns 4

Constraints

• 1 <= capacity <= 3000.
• 0 <= key, value <= 10^4.
• At most 2 * 10^5 calls to get and put combined.
• Both get and put must run in O(1) average time.

Given the head of a singly linked list, determine whether it reads the same forwards and backwards (i.e., its sequence of values is a palindrome). Return True or False.

Example 1

Input:  1 -> 2 -> 2 -> 1 -> None
Output: True

Example 2

Input:  1 -> 2 -> 3 -> None
Output: False

Example 3

Input:  7 -> None
Output: True

Constraints

• The number of nodes is in the range [1, 10^5].
• 0 <= Node.val <= 9.
• Solve it in O(n) time. As a follow-up, try O(1) extra space instead of copying values into an array.

You are given a doubly linked list where, in addition to the next and prev pointers, each node may have a child pointer to a separate doubly linked list. That child list may itself contain nodes with their own child pointers, nested to any depth. Flatten the list so that all nodes appear in a single-level doubly linked list, in depth-first order: whenever a node has a child, the entire child list (flattened) is spliced in immediately after that node and before its original next. After flattening, every child pointer must be set to None.

Input (top level, with a child list under node 3):
1 -> 2 -> 3 -> 4 -> 5 -> None
          |
          7 -> 8 -> None
               |
               9 -> None

Output (flattened, depth-first):
1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 4 -> 5 -> None

Example

Input:  head = 1 <-> 2 <-> 3 <-> None, with 2.child = 4 <-> 5 <-> None
Output: 1 <-> 2 <-> 4 <-> 5 <-> 3 <-> None

Constraints

• The number of nodes across all levels is at most 1000.
• child pointers may be None for most nodes.
• Aim for O(n) time, visiting each node once.