DSA + System design - 10

Given a linked list, how can you detect if it contains a cycle?

• Use a hash table to store visited nodes

• Use two pointers, one moving twice as fast as the other

• Use a counter to count nodes

• Traverse the Linkedlist till Null not found

How do you reverse a singly linked list in O(n) time?

• Swap the values of nodes starting from the two ends

• Change the next pointers of each node to point to the previous node

• Use a stack to store all nodes and then pop them

• Use recursion to reach end node and then link back to previous nodes while rolling back

How do you merge two sorted linked lists into a single sorted linked list?

• Concatenate the lists and sort the resulting list

• Use a priority queue

• Traverse both lists and merge them using a dummy node

• Use a hash table to store elements

What is the best way to remove duplicates from an unsorted linked list?

• Sort the list and remove duplicates

• Use a hash table to track seen elements

• Compare each element with every other element

• Use a stack to track duplicates

How do you check if a linked list is a palindrome?

• Reverse the list and compare with the original

• Use a stack to compare the first half with the second half

• Recurse till last node then compare back nodes with front nodes

• All of the above

How do you delete a node from a singly linked list given only a pointer to that node?

• Copy data from the next node and delete the next node

• Traverse the list to find the previous node and delete the current node

• Mark the node as deleted without removing it

• Not possible without head pointer

How can you determine if two singly linked lists intersect?

• Compare each node of one list with each node of the other

• Use a hash table to store nodes of one list and check against the other

• Find the lengths of both lists and compare the tails

• None of the above

What is the time complexity to insert a node at the beginning of a singly linked list?

• O(1)

• O(n)

• O(log n)

• O(n log n)

What is the time complexity of reversing a doubly linked list?

• O(1)

• O(n)

• O(n log n)

• O(n^2)

In a circular linked list, how can you determine the length of the list?

• Count nodes until you revisit the head

• Use a hash table to detect cycles

• Both a and b

• None of the above