10 Data Structures Linked List Interview Questions and Answers

Linked lists are a fundamental data structure in computer science, offering a dynamic and flexible way to store and manage data. Unlike arrays, linked lists allow for efficient insertion and deletion of elements without the need for reallocation or reorganization of the entire structure. This makes them particularly useful in scenarios where the size of the data set is unpredictable or frequently changing.

This article provides a curated selection of interview questions focused on linked lists, designed to help you understand and articulate key concepts during your interview. By working through these questions, you’ll gain a deeper understanding of linked lists and be better prepared to demonstrate your knowledge and problem-solving abilities.

Data Structures Linked List Interview Questions and Answers

1. Write a function to insert a node at the beginning, middle, and end of a singly linked list.

To insert a node at the beginning, middle, and end of a singly linked list, handle three cases:

1. Update the head for the beginning.
2. Traverse to the desired position for the middle and update pointers.
3. Traverse to the last node for the end and update its next pointer.

Here’s a concise implementation in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def insert_at_middle(self, prev_node, data):
        if not prev_node:
            print("Previous node must be in the LinkedList.")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node

# Example usage:
ll = LinkedList()
ll.insert_at_beginning(1)
ll.insert_at_end(3)
ll.insert_at_middle(ll.head, 2)

2. Implement a function to traverse a linked list and print all its elements.

Traversing a linked list involves starting from the head node and moving through each node until the end is reached. Here’s a simple implementation in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def traverse(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

# Example usage:
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.traverse()

3. Write a function to search for a given value in a linked list.

To search for a value in a linked list, traverse from the head to the end, comparing each node’s data with the target value. Here’s a simple implementation:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def search_linked_list(head, target):
    current = head
    while current is not None:
        if current.data == target:
            return True
        current = current.next
    return False

# Example usage:
# Creating a linked list: 1 -> 2 -> 3 -> 4
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)

# Searching for value 3
print(search_linked_list(head, 3))  # Output: True

# Searching for value 5
print(search_linked_list(head, 5))  # Output: False

4. Write a function to detect a cycle in a linked list using Floyd’s Cycle-Finding Algorithm.

Floyd’s Cycle-Finding Algorithm, or the Tortoise and Hare algorithm, detects cycles in a linked list using two pointers, one moving twice as fast as the other. If there’s a cycle, the fast pointer will meet the slow pointer.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

5. Implement a function to reverse a singly linked list.

Reversing a singly linked list involves changing the direction of the pointers so each node points to its previous node. Here’s a simple implementation:

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

6. Write a function to merge two sorted linked lists into one sorted linked list.

To merge two sorted linked lists into one, use a two-pointer technique. Iterate through both lists, comparing nodes, and append the smaller node to the merged list. Continue until both lists are traversed.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    current = dummy

    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    current.next = l1 if l1 else l2

    return dummy.next

7. Implement a function to find the middle element of a linked list in a single pass.

To find the middle element of a linked list in a single pass, use two pointers: slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def find_middle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow.value

# Example usage:
# Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(find_middle(head))  # Output: 3

8. Write a function to remove duplicate values from an unsorted linked list.

To remove duplicate values from an unsorted linked list, use a set to track encountered values. Traverse the list, checking if the current node’s value is in the set. If it is, remove the node; otherwise, add the value to the set.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def remove_duplicates(head):
    if not head:
        return head

    current = head
    seen = set([current.value])
    while current.next:
        if current.next.value in seen:
            current.next = current.next.next
        else:
            seen.add(current.next.value)
            current = current.next

    return head

9. Implement a function to find the kth element from the end of a linked list.

To find the kth element from the end of a linked list, use two pointers. Move the first pointer k steps ahead, then move both pointers simultaneously until the first reaches the end. The second pointer will be at the kth element from the end.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def find_kth_from_end(head, k):
    first = head
    second = head

    for _ in range(k):
        if first is None:
            return None
        first = first.next

    while first:
        first = first.next
        second = second.next

    return second.value

# Example usage:
# Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(find_kth_from_end(head, 2))  # Output: 4

10. Write a function to flatten a multilevel linked list where each node may have a next and a child pointer.

A multilevel linked list has nodes with next and child pointers. Flattening involves integrating child nodes into the main list using a depth-first search approach.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.child = None

def flatten_list(head):
    if not head:
        return head

    current = head
    while current:
        if current.child:
            child = current.child
            next_node = current.next
            current.next = child
            current.child = None

            temp = child
            while temp.next:
                temp = temp.next
            temp.next = next_node

        current = current.next

    return head