Top 10 Linked List Interview Questions and Answers in Python

on

 


Common Linked List Interview Questions & Their Solutions

Introduction

    Linked Lists are one of the most common data structures in coding interviews. They test your understanding of pointers, memory management, and algorithmic thinking. In this, we’ll look at some frequently asked Linked List interview questions and their Python solutions.

Question 1: Reverse a Linked List

Problem:
Given the head of a singly linked list, reverse the list.

Python Code:

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

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

Key Idea:
We use three pointers (prev, current, next_node) to reverse the direction of links one by one.

Question 2: Find the Middle Node of a Linked List

Problem:
Return the middle node of a linked list in one traversal.

Python Code:

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Concept:
Use the two-pointer technique — the fast pointer moves twice as fast as the slow one.

Question 3: Detect a Cycle in a Linked List

Problem:
Check whether a linked list contains a cycle.

Python Code:

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Concept:
This uses Floyd’s Cycle Detection Algorithm (also called the Tortoise and Hare algorithm).

Question 4: Merge Two Sorted Linked Lists

Problem:
Combine two sorted linked lists into a single sorted list.

Python Code:

def merge_sorted_lists(l1, l2):
    dummy = Node(0)
    tail = dummy
    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2
    return dummy.next

Question 5: Remove Duplicates from a Sorted Linked List

Python Code:

def remove_duplicates(head):
    current = head
    while current and current.next:
        if current.data == current.next.data:
            current.next = current.next.next
        else:
            current = current.next
    return head

Question 6: Find the Nth Node from the End

Problem:
Given the head of a linked list, find the Nth node from the end in one pass.

Python Code:

def nth_from_end(head, n):
    first = second = head
    for _ in range(n):
        if not first:
            return None
        first = first.next
    while first:
        first = first.next
        second = second.next
    return second

Concept:
Move the first pointer n steps ahead, then move both pointers until the first reaches the end.

Question 7: Delete a Node Without Head Pointer

Problem:
You’re given only a pointer to a node to delete (not the head). Delete the node efficiently.

Python Code:

def delete_node(node):
    if node and node.next:
        node.data = node.next.data
        node.next = node.next.next

Concept:
Copy the data of the next node and bypass it — no need for head reference.

Question 8: Check if Two Linked Lists Intersect

Problem:
Determine whether two linked lists intersect and return the intersection point.

Python Code:

def get_intersection_node(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a

Concept:
Both pointers traverse each list and then switch — ensuring equal traversal length.

Question 9: Remove Nth Node from End

Problem:
Remove the Nth node from the end of a linked list.

Python Code:

def remove_nth_from_end(head, n):
    dummy = Node(0)
    dummy.next = head
    first = second = dummy
    for _ in range(n + 1):
        first = first.next
    while first:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

Concept:
Use a dummy node and two-pointer approach to simplify deletion logic.

Question 10: Check if a Linked List is a Palindrome

Problem:
Return True if the linked list reads the same forward and backward.

Python Code:

def is_palindrome(head):
    slow = fast = head
    stack = []
    while fast and fast.next:
        stack.append(slow.data)
        slow = slow.next
        fast = fast.next.next
    if fast:
        slow = slow.next
    while slow:
        if stack.pop() != slow.data:
            return False
        slow = slow.next
    return True

Concept:
Use a stack to compare the first half and the reversed second half of the list.

Summary

You’ve now learned 10 of the most frequently asked Linked List interview questions, covering:
- Traversal and manipulation
- Two-pointer techniques
- Cycle and intersection logic
- Palindrome detection

These are essential for coding interviews at top companies (TCS, Infosys, Wipro, etc.) and for competitive programming practice.



Comments

Post a Comment