๐ Linked Lists
๐ 21. How do you reverse a singly linked list?
A singly linked list can be reversed by changing the direction of pointers.
๐น Example
Before:
1 โ 2 โ 3 โ NULL
After:
3 โ 2 โ 1 โ NULL
๐น Iterative Solution
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
๐น Complexity
Time โ O(n)
Space โ O(1)
๐น Interview Tip
This is one of the most important linked-list questions.
๐ 22. How do you detect a cycle in a linked list?
Use Floydโs Cycle Detection Algorithm.
Also called: Tortoise and Hare Algorithm
๐น Idea
โข Slow pointer moves 1 step
โข Fast pointer moves 2 steps
โข If they meet โ cycle exists
๐น Python Solution
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
๐น Complexity
Time โ O(n)
Space โ O(1)
๐น Interview Tip
Very common interview question.
๐ 23. How do you find the middle node of a linked list?
Use two pointers.
๐น Approach
โข Slow pointer โ moves 1 step
โข Fast pointer โ moves 2 steps
When fast reaches end:
slow = middle
๐น Python Solution
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
๐น Complexity
Time โ O(n)
Space โ O(1)
๐น Interview Tip
Two-pointer technique is heavily used in linked lists.
๐ 24. How do you merge two sorted linked lists?
๐น Example
1 โ 3 โ 5
2 โ 4 โ 6
Merged:
1 โ 2 โ 3 โ 4 โ 5 โ 6
๐น Python Solution
def merge_lists(l1, l2):
dummy = Node(0)
current = dummy
while l1 and l2:
if l1.data < l2.data:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
๐น Complexity
Time โ O(n + m)
Space โ O(1)
๐น Interview Tip
This problem is the base concept behind merge sort on linked lists.
๐ 25. How do you find and remove a duplicate in a list?
๐น Using HashSet
def remove_duplicates(head):
seen = set()
current = head
prev = None
while current:
if current.data in seen:
prev.next = current.next
else:
seen.add(current.data)
prev = current
current = current.next
return head
๐น Complexity
Time โ O(n)
Space โ O(n)
๐น Without Extra Space
Can also be solved using nested loops: O(nยฒ)
๐น Interview Tip
Interviewers may ask: Can you solve it without extra memory?
๐ 26. How do you implement a dummy head in linked-list problems?
A dummy node simplifies edge cases.
๐น Why Useful?
Without dummy node: Handling head insertion/deletion becomes complex
With dummy node: Logic becomes cleaner
๐น Example
dummy = Node(0)
dummy.next = head
๐น Use Cases
โ Remove nodes
โ Merge lists
โ Partition lists
โ Reverse sublists
๐น Interview Tip
Using dummy nodes often makes solutions cleaner and bug-free.
๐ 27. How do you delete a node given only that node (no head)?
Important constraint: No access to head pointer
๐น Trick
Copy next node value into current node.
๐น Python Solution
def delete_node(node):
node.data = node.next.data
node.next = node.next.next
๐น Limitation
Cannot delete last node because no next node exists.
๐น Interview Tip
Classic interview trick question.