Linked Lists Flashcards
How will you implement a Linked List?
By connecting Nodes
How will you detect a cycle?
With tortoise and hare algorithm
How will you find middle element?
Use Tortoise and Hare algorithm or just divide the size by two and with usage of for loop get to the middle
How will you reverse a Linked List?
You have to move the elements to the left by one. To do this, use pointers prev and next, where next will store the next current value when current->next = prev and the current value will be assigned to the prev pointer. Make the update on the current pointer and in the end just assign prev pointer to head to make the last element meant by head.
How will you merge two sorted Linked Lists?
By reference to them and pushing back their data
How will you check if the Linked List is a palindrome?
If the reversed list is equal to the basic one
ARRAY QUESTION
How will you remove Nth node from the end?
By using size parameter, size - n and for loop
The advantages and disadvantages between Linked lists and Arrays
Linked List have constant time in adding at front and Arrays have amortized adding at back. The main difference is that linked lists are better situated in memory, and you have that constant time in pushing and poping at the front.
Which implementation of find middle element is faster:
- Tortoise and Hare algorithm
- middle is equal to size / 2 and next is to use loop
Tortoise and Hare algorithm is faster.
What is the difference between while( current != nullptr and current->next != nullptr )
The difference relies on when you use the current != nullptr the loop ends on the nullptr and when you use the second option with current->next != nullptr you will end on the last element in the linked list.
