Linked Lists Questions Placement

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

1. "Can you do it with O(1) space?" → Optimize by modifying pointers in-place
2. "Handle the edge case of single node" → Always test with minimal inputs
3. "What if the list is circular?" → Modify algorithm to detect and handle cycles
4. "Recursive vs iterative solution?" → Recursive uses O(n) stack space
5. "Doubly linked list version?" → Update both next and prev pointers

---

Companies Asking Linked List Questions

Company	Frequency	Common Questions
Google	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

1. Master Pointer Manipulation: Practice drawing diagrams before coding
2. Use Dummy Nodes: They simplify edge cases significantly
3. Learn Two-Pointer Patterns: Slow/fast pointers solve many problems elegantly
4. Practice Recursion: Some problems have elegant recursive solutions
5. Handle Edge Cases: Empty list, single node, two nodes
6. Draw It Out: Visualize pointer changes on paper first
7. Test Tracing: Walk through your code with a small example

---

You May Also Like

• Linked List Interview Questions 2026

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! 🚀