Linked Lists Questions Placement
Linked Lists Interview Questions and Answers for Placements
Last Updated: March 2026
Introduction to Linked Lists
Linked lists are fundamental data structures that play a crucial role in technical interviews at top tech companies like Google, Amazon, Microsoft, and Flipkart. Unlike arrays, linked lists store elements in nodes where each node contains data and a reference to the next node, allowing dynamic memory allocation and efficient insertions/deletions.
Why Linked Lists Are Important for Placements
- FAANG Interview Staple: Every major tech company asks linked list questions
- Foundation for Advanced Structures: Trees, graphs, and hash maps build upon linked list concepts
- Memory Management: Tests understanding of pointers/references and dynamic allocation
- Problem-Solving Skills: Requires logical thinking for traversal, reversal, and manipulation
Key Concepts and Theory
Types of Linked Lists
1. Singly Linked List
- Each node points to the next node only
- Traversal is unidirectional
- Last node points to NULL
class Node:
def __init__(self, data):
self.data = data
self.next = None
2. Doubly Linked List
- Each node has pointers to both next and previous nodes
- Bidirectional traversal possible
- Requires more memory per node
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
3. Circular Linked List
- Last node points back to the first node
- Useful for round-robin scheduling
- No NULL termination
Time Complexity Comparison
| Operation | Array | Linked List |
|---|---|---|
| Access | O(1) | O(n) |
| Search | O(n) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1)* | O(1)** |
| Delete | O(n) | O(1)*** |
| Memory | Contiguous | Dynamic |
*Amortized for dynamic arrays **With tail pointer ***With node reference
Practice Questions with Solutions
Question 1: Reverse a Linked List ⭐ [Easy]
Problem: Reverse a singly linked list iteratively.
Solution:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
Explanation: We use three pointers - prev, current, and next_temp. For each node, we store the next node, reverse the link, and move forward. Time: O(n), Space: O(1).
Question 2: Detect Cycle in Linked List ⭐⭐ [Medium]
Problem: Determine if a linked list has a cycle using Floyd's algorithm.
Solution:
def hasCycle(head):
if not head or not head.next:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Explanation: The tortoise and hare approach - slow moves 1 step, fast moves 2 steps. If they meet, there's a cycle. If fast reaches NULL, no cycle exists.
Question 3: Find the Middle of Linked List ⭐ [Easy]
Problem: Return the middle node of a linked list in one pass.
Solution:
def middleNode(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Explanation: Fast pointer moves twice as fast as slow. When fast reaches end, slow is at middle.
Question 4: Merge Two Sorted Linked Lists ⭐⭐ [Medium]
Problem: Merge two sorted linked lists into one sorted list.
Solution:
def mergeTwoLists(list1, list2):
dummy = ListNode(0)
current = dummy
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 if list1 else list2
return dummy.next
Explanation: Use a dummy node to simplify edge cases. Compare nodes and append smaller one. Time: O(n+m), Space: O(1).
Question 5: Remove Nth Node from End ⭐⭐ [Medium]
Problem: Remove the nth node from the end of the list.
Solution:
def removeNthFromEnd(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Move fast n+1 steps ahead
for _ in range(n + 1):
fast = fast.next
# Move both until fast reaches end
while fast:
fast = fast.next
slow = slow.next
# Remove the node
slow.next = slow.next.next
return dummy.next
Explanation: Two-pointer technique. Fast pointer creates a gap of n+1, then both move together. When fast hits NULL, slow is at the node before target.
Question 6: Intersection of Two Linked Lists ⭐⭐ [Medium]
Problem: Find the node where two linked lists intersect.
Solution:
def getIntersectionNode(headA, headB):
if not headA or not headB:
return None
ptrA, ptrB = headA, headB
while ptrA != ptrB:
ptrA = ptrA.next if ptrA else headB
ptrB = ptrB.next if ptrB else headA
return ptrA
Explanation: When a pointer reaches end, redirect to other's head. They'll meet at intersection or both become NULL. Time: O(n+m), Space: O(1).
Question 7: Palindrome Linked List ⭐⭐⭐ [Hard]
Problem: Check if a linked list is a palindrome in O(n) time and O(1) space.
Solution:
def isPalindrome(head):
if not head or not head.next:
return True
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
while slow:
next_temp = slow.next
slow.next = prev
prev = slow
slow = next_temp
# Compare first and second half
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
Explanation: Find middle, reverse second half, compare, and (optionally) restore. This achieves O(1) extra space.
Question 8: Copy List with Random Pointer ⭐⭐⭐ [Hard]
Problem: Deep copy a linked list where each node has a random pointer.
Solution:
def copyRandomList(head):
if not head:
return None
# Step 1: Create copy nodes interleaved
current = head
while current:
new_node = Node(current.val)
new_node.next = current.next
current.next = new_node
current = new_node.next
# Step 2: Assign random pointers
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Step 3: Separate the lists
current = head
new_head = head.next
while current:
copy = current.next
current.next = copy.next
if copy.next:
copy.next = copy.next.next
current = current.next
return new_head
Explanation: Three-pass approach: interleave copies, set random pointers, then separate. No hash map needed.
Question 9: LRU Cache Implementation ⭐⭐⭐ [Hard]
Problem: Design an LRU Cache with O(1) get and put operations.
Solution:
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
prev, nxt = node.prev, node.next
prev.next, nxt.prev = nxt, prev
def _add(self, node):
prev, nxt = self.tail.prev, self.tail
prev.next = node
nxt.prev = node
node.prev = prev
node.next = nxt
def get(self, key):
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.val
return -1
def put(self, key, val):
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, val)
self._add(node)
self.cache[key] = node
if len(self.cache) > self.capacity:
lru = self.head.next
self._remove(lru)
del self.cache[lru.key]
Explanation: Combine hash map for O(1) access with doubly linked list for O(1) removal/addition at both ends.
Question 10: Flatten a Multilevel Doubly Linked List ⭐⭐⭐ [Hard]
Problem: Flatten a multilevel doubly linked list into a single-level sorted list.
Solution:
def flatten(head):
if not head:
return head
dummy = Node(0)
dummy.next = head
head.prev = dummy
stack = [head]
prev = dummy
while stack:
curr = stack.pop()
prev.next = curr
curr.prev = prev
if curr.next:
stack.append(curr.next)
if curr.child:
stack.append(curr.child)
curr.child = None
prev = curr
dummy.next.prev = None
return dummy.next
Explanation: Use stack for DFS traversal. Process child before next to maintain order. Time: O(n), Space: O(n).
Common Interview Follow-Up Questions
- "Can you do it with O(1) space?" → Optimize by modifying pointers in-place
- "Handle the edge case of single node" → Always test with minimal inputs
- "What if the list is circular?" → Modify algorithm to detect and handle cycles
- "Recursive vs iterative solution?" → Recursive uses O(n) stack space
- "Doubly linked list version?" → Update both next and prev pointers
Companies Asking Linked List Questions
| Company | Frequency | Common Questions |
|---|---|---|
| Very High | LRU Cache, Copy Random Pointer | |
| Amazon | Very High | Reverse, Merge, Detect Cycle |
| Microsoft | High | Palindrome, Intersection |
| Facebook/Meta | Very High | Deep Copy, Flatten List |
| Apple | High | Remove Nth from End |
| Adobe | Medium | Middle Element, Reverse in groups |
| Oracle | Medium | Sorting, Rearrangement |
| Salesforce | Medium | Cycle detection, Reordering |
Preparation Tips
- Master Pointer Manipulation: Practice drawing diagrams before coding
- Use Dummy Nodes: They simplify edge cases significantly
- Learn Two-Pointer Patterns: Slow/fast pointers solve many problems elegantly
- Practice Recursion: Some problems have elegant recursive solutions
- Handle Edge Cases: Empty list, single node, two nodes
- Draw It Out: Visualize pointer changes on paper first
- Test Tracing: Walk through your code with a small example
FAQ
Q: Array vs Linked List - when to use which?
A: Use arrays for frequent access by index, cache-friendly operations. Use linked lists for frequent insertions/deletions, unknown size, or when memory fragmentation matters.
Q: Why is LRU Cache considered a linked list problem?
A: It combines hash map (O(1) lookup) with doubly linked list (O(1) removal/addition at ends) for optimal access patterns.
Q: What's the best way to practice linked lists?
A: Start with basic operations (insert, delete, traverse), then move to LeetCode Easy → Medium → Hard. Focus on patterns, not memorization.
Q: Do interviewers ask about circular linked lists?
A: Yes, but less frequently. Know how to detect cycles (Floyd's) and find the start of cycle.
Q: Should I know doubly linked list operations?
A: Absolutely. Many advanced problems require updating both next and prev pointers.
Keep practicing, and good luck with your placements! 🚀