Quick wins for a faster PC:
Fix the driver behind crashes, sound loss and screen glitchesFind Drivers →Clear out junk files and repair common Windows errorsFree Scan →Scan for outdated or missing drivers - takes under a minuteDriver Scan →These 25 linked-list interview questions cover Java’s collection API, pointer fundamentals, common algorithms, and data-structure design. For coding exercises, first clarify whether the interviewer expects a custom node-based list or java.util.LinkedList: the collection does not expose its internal links, so classic pointer-rewiring problems need a custom Node structure.
Start with the Java and data-structure fundamentals
1. What is a linked list, and how does a node refer to its successor?
A linked list stores elements in nodes. In a singly linked list, each node holds a value and a reference to the next node; the list typically tracks its first node, called the head. Unlike an array-backed structure, nodes need not occupy adjacent memory locations.
2. How do singly linked, doubly linked, and circular lists differ?
- Singly linked: each node points forward. It uses one link per node, but moving backward requires another traversal or extra bookkeeping.
- Doubly linked: each node points to both its predecessor and successor. It supports movement in both directions, at the cost of an additional reference and more link updates.
- Circular: the final node links back to an earlier node, often the head. Traversal needs a stopping condition other than reaching
null.
3. What are the time and space costs of common singly linked-list operations?
Searching for a value and traversing the list take O(n) time. Inserting at the head takes O(1); appending takes O(1) if a tail reference is maintained, otherwise finding the end takes O(n). Deleting a node by value generally takes O(n) because the list must find it and, in a singly linked list, its predecessor. Inserting or deleting is O(1) once the relevant position and any required predecessor are already available. Each node takes O(1) storage, so the list takes O(n) space.
4. How would you implement a generic Node<T> and a minimal singly linked list in Java?
Use a node with a value and a next reference, such as class Node<T> { T value; Node<T> next; }. A minimal list can track head and optionally tail and size. Keep node links and list state private where appropriate, and define how null values, empty lists, and size updates are handled. Use this custom representation for pointer exercises; use the standard collection when the prompt asks about the Java API.
#1 Best Overall
5. What invariants should head, tail, and size satisfy?
- Empty:
size == 0; bothheadandtailarenull. - One node:
head == tail; the node’snextisnull. - Multiple nodes:
headis the first node,tailis the last, andtail.next == null.
Every insertion and removal must preserve these relationships and update size exactly once.
6. When should you choose Java LinkedList over ArrayList?
Choose based on the operations and workload, not the claim that a linked list is automatically faster at insertion. Oracle documents LinkedList<E> as a doubly linked implementation of List and Deque. Its indexed operations traverse from the nearer end; ArrayList is generally the more natural choice for frequent indexed reads. In either structure, finding an insertion position can dominate the cost: a linked list only offers constant-time link changes after the location is known. A linked list can also serve as a deque. Its node-based layout has different memory and locality characteristics from an array-backed list, so assess the actual use case. See Oracle’s Java SE 26 LinkedList API and Java SE 26 List API.
Practice pointer patterns and core algorithms
For each coding prompt, state assumptions, walk through a small example, explain the pointer invariant, and test relevant boundary cases. Give time and auxiliary-space complexity, and distinguish a custom node algorithm from operations on a Java collection.
7. How do you reverse a singly linked list iteratively?
Use three references: previous, current, and next. Before redirecting current.next to previous, save the original next node so the unprocessed suffix is not lost. Advance both references and return previous as the new head. The loop takes O(n) time and O(1) auxiliary space; an empty list remains empty.
Recommended Free Tools
8. How do you reverse a singly linked list recursively?
Use the empty-list and one-node cases as the base case. Recursively reverse the suffix, then make the former second node point back to the current node and set the current node’s next to null. Return the new head. This takes O(n) time and O(n) call-stack space; recursion depth may be unsuitable for very long lists.
9. How do you find the middle node in one traversal?
Advance a slow pointer by one node and a fast pointer by two. When the fast pointer reaches the end, the slow pointer is at the middle. With the common loop condition that requires both fast and fast.next to exist, an even-length list returns the second of its two middle nodes. The method takes O(n) time and O(1) auxiliary space.
10. How do you find the kth node from the end?
Clarify that k is one-based: k == 1 means the final node. Advance a lead pointer k nodes, then advance it alongside a following pointer until the lead reaches the end. If k is zero, negative, or larger than the list length, reject it or return the prompt’s specified no-result value. This takes O(n) time and O(1) auxiliary space.
11. How do you detect a cycle in a singly linked list?
Use Floyd’s slow/fast pointer technique: move one pointer by one link and the other by two. If they meet, a cycle exists; if the fast pointer reaches null or its next link is null, the list is acyclic. The method takes O(n) time and O(1) auxiliary space.
Rank #3
12. If a cycle exists, how do you find its starting node?
After the slow and fast pointers meet, put one pointer back at the head. Move both one node at a time; their next meeting point is the cycle entry. This relies on the distance relationship between the non-cyclic prefix and the cycle length. Explain that relationship rather than treating the result as a trick. Detection and entry finding take O(n) time and O(1) auxiliary space.
13. How do you merge two sorted singly linked lists?
Use a dummy head and repeatedly attach the smaller current node, then append whichever list remains. Reuse nodes if the prompt allows it; otherwise allocate new nodes. This handles an empty input naturally and preserves duplicate values. It takes O(m + n) time for lists of lengths m and n; auxiliary space is O(1) when reusing nodes, excluding a dummy node.
14. How do you remove a node by value?
Specify whether to remove the first matching node or every match. For the first match, handle a head match separately or use a dummy node, then track the predecessor while searching. If no value matches, leave the list unchanged. Update the tail and size if the list tracks them. The search takes O(n) time and O(1) auxiliary space.
15. How do you remove the kth node from the end in one pass?
Use a dummy node before the head. Advance a lead pointer k steps from the dummy, then move it and a trailing pointer together until the lead reaches the final node. The trailing pointer then precedes the node to remove. With one-based k, define behavior for k <= 0 or k greater than the length; do not silently remove the head for an invalid request. This takes O(n) time and O(1) auxiliary space.
16. How do you check whether a linked list is a palindrome?
One straightforward method copies values into an array or stack and compares from both ends; it takes O(n) time and O(n) extra space. To reduce auxiliary space, find the midpoint, reverse the second half, compare corresponding values, and restore the reversed half if the caller expects the original list to remain unchanged. That approach takes O(n) time and O(1) auxiliary space, excluding pointers.
17. How do you find the intersection of two singly linked lists?
Intersection means the lists share the same node by reference identity, not merely nodes with equal values. A two-pointer method sends one pointer along each list, then switches each to the other list’s head upon reaching the end. If an intersection exists, the pointers meet there; if not, both eventually reach null. The method takes O(m + n) time and O(1) auxiliary space.
18. How do you remove duplicates from sorted and unsorted lists?
In a sorted list, compare adjacent values and unlink repeated nodes in one pass, using O(1) auxiliary space. For an unsorted list, a set can record values already seen, allowing one traversal at O(n) expected time and O(n) extra space. If extra memory is disallowed, compare each node with later nodes; that uses O(1) extra space but takes O(n²) time.
19. How do you add two numbers stored as reverse-order digit lists?
Each node represents one digit, starting with the ones place. Add corresponding digits and a carry, append the result digit, and continue while either list or a carry remains. This naturally handles unequal lengths; for example, a final carry becomes a new node. For lengths m and n, time is O(max(m, n)) and output storage is O(max(m, n) + 1) in the carry case.
Crashes, No Sound, or Screen Glitches?
Random freezes, missing sound and display glitches usually trace back to one bad driver. Find and replace yours safely.Free scan · under a minutePC Slower Than It Used to Be?
A free scan shows the junk files, broken settings and background clutter dragging Windows down - then fixes them in one click.Free scan · Windows 10 & 1120. How do you partition a list around a pivot?
Clarify whether relative order must be preserved. For a stable partition, build lower-than-pivot and greater-than-or-equal-to-pivot chains in traversal order, then join them. Ensure both chain tails terminate at null to avoid stale links or cycles. This takes O(n) time and O(1) auxiliary space when relinking existing nodes; a version that allocates new nodes uses additional output space.
21. How do you rotate a list by k positions?
Clarify whether rotation is to the right or left. For a right rotation, find the length, normalize k with k % length, connect the tail to the head temporarily, and break the cycle at the new tail. Return unchanged for an empty list or a normalized rotation of zero. This takes O(n) time and O(1) auxiliary space.
Discuss linked-list design and Java API behavior
22. How do you insert into or delete from a doubly linked list?
For insertion, update both directions: the new node’s prev and next, the neighboring nodes’ corresponding links, and the head or tail when the insertion is at an endpoint. For deletion, connect the target’s predecessor to its successor in both directions, again handling head and tail separately. State the invariant that every adjacent pair agrees: if x.next == y, then y.prev == x.
23. How would you design an LRU cache?
Combine a hash map from keys to list nodes with a doubly linked list ordered from most recently used to least recently used. The map provides direct node lookup; the list allows a known node to be moved or removed in O(1). On access, move the node to the most-recent end. On insertion beyond capacity, evict the least-recent node and remove its key from the map. Explain how updates, capacity zero, and synchronization are handled.
The Tool Desk
Outbyte PC Repair FREEClear out junk files and repair common Windows errorsFree Scan →Outbyte Driver Updater FREEScan for outdated or missing drivers - takes under a minuteDriver Scan →24. When is java.util.LinkedList useful as a deque?
Use deque operations when the program needs work at both ends rather than frequent indexed reads. Oracle’s API provides addFirst, addLast, removeFirst, and removeLast; push and pop express stack-style operations at the front. Choose the method whose behavior communicates the intended queue or stack use. The class permits null elements, so account for that if null values could be confused with an empty-result signal.
25. What does fail-fast iteration mean, and can it provide thread safety?
Oracle describes LinkedList iterators as fail-fast: they may throw ConcurrentModificationException after structural modification outside the iterator. This is best-effort bug detection, not a guarantee. The class is not synchronized, and code must not rely on the exception for correctness or thread safety. See the Oracle Java SE 26 LinkedList documentation.
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
