Learning about linked lists is important from an interview point of view because linked lists are a fundamental data structure in computer science, and they are frequently used in interview questions and programming challenges.
Linked lists are used to store a collection of data elements that are connected together in a sequence. They are used to implement many other data structures, such as stacks, queues, trees, and graphs. In addition, linked lists have several properties that make them useful in certain contexts, such as constant-time insertion and deletion of elements, and the ability to store elements in a non-contiguous memory block.
During coding interviews, interviewers often use linked list questions to test a candidate’s ability to understand and manipulate fundamental data structures. Questions about linked lists can range from simple operations like inserting, deleting, and searching for elements, to more complex algorithms like merging two sorted linked lists, reversing a linked list, or detecting a cycle in a linked list.
In addition, linked list questions can test a candidate’s understanding of pointers, memory allocation, and algorithmic complexity. Candidates who are comfortable working with linked lists are often better equipped to solve a wide range of programming problems and are more likely to succeed in technical interviews.
What is a linked list and how is it different from an array?
A linked list is a linear data structure in which elements are stored in nodes, each of which contains a value and a pointer to the next node. The first node is called the head of the linked list, and the last node has a null pointer to indicate the end of the list. Linked lists can be singly linked (each node only points to the next node) or doubly linked (each node points to both the next and previous nodes).
An array is also a linear data structure, but it stores elements in contiguous memory locations. Array elements can be accessed directly using their index, which is an integer offset from the beginning of the array.
The main differences between linked lists and arrays are:
- Memory allocation: Arrays require contiguous memory allocation, while linked lists use dynamic memory allocation, where each node is allocated memory separately as it is needed.
- Size: Arrays have a fixed size, whereas linked lists can grow or shrink dynamically as nodes are added or removed.
- Accessing elements: Arrays provide constant-time access to any element using its index, whereas accessing an element in a linked list requires traversing the list from the head until the desired node is found.
- Insertion and deletion: Insertion and deletion of elements in an array can be expensive because it requires shifting all the elements after the insertion or deletion point. In contrast, insertion and deletion in a linked list can be done more efficiently by changing the pointers of the nodes involved.
How do you traverse a linked list?
To traverse a linked list, you need to start at the head of the list and visit each node in the list until you reach the end. Here is an example of how to do this in pseudocode:
current_node = head
while current_node is not null:
// Do something with the current node, such as printing its value
print(current_node.value)
// Move to the next node
current_node = current_node.next
In this code, we start with the head of the linked list and set current_node to point to it. We then enter a loop that continues as long as current_node is not null (indicating that we have reached the end of the list).
Inside the loop, we can perform any operation we want on the current node, such as printing its value. We then move to the next node by setting current_node to point to the next node in the list.
This loop will continue until we have visited every node in the linked list, after which current_node will be null and the loop will terminate.
How do you find the middle element of a linked list?
To find the middle element of a linked list, we can use the two-pointer technique, which is also known as the “slow and fast pointer” approach. Here is an example of how to do this in pseudocode:
slow_ptr = head
fast_ptr = head
while fast_ptr is not null and fast_ptr.next is not null:
// Move the slow pointer one node at a time
slow_ptr = slow_ptr.next
// Move the fast pointer two nodes at a time
fast_ptr = fast_ptr.next.next
// At this point, the slow pointer is at the middle node
print(slow_ptr.value)
In this code, we start with two pointers, slow_ptr and fast_ptr, both pointing to the head of the linked list. We then enter a loop that continues as long as fast_ptr is not null and fast_ptr.next is not null (indicating that we have not reached the end of the list yet).
Inside the loop, we move the slow pointer one node at a time by setting slow_ptr to point to the next node in the list. We also move the fast pointer two nodes at a time by setting fast_ptr to point to the next.next node in the list.
When the loop ends, the slow pointer will be pointing to the middle node of the linked list (or the node just before the middle node if the list has an even number of nodes). We can then print the value of the middle node, or perform any other operation we want on it.
How do you reverse a linked list?
To reverse a linked list, we need to change the pointers of each node so that they point in the opposite direction. We can do this by iterating over the list and swapping the next pointer of each node with its previous pointer (which initially points to null for the first node). Here is an example of how to do this in pseudocode:
prev = null
current = head
while current is not null:
// Store the next node before we change the current node's pointer
next_node = current.next
// Reverse the current node's pointer to point to the previous node
current.next = prev
// Move the pointers one node ahead
prev = current
current = next_node
// At this point, the prev pointer is the new head of the reversed list
print(prev.value)
In this code, we start with two pointers, prev and current, both pointing to null and the head of the linked list, respectively. We then enter a loop that continues as long as current is not null.
Inside the loop, we store the next node in a temporary variable called next_node so that we can access it after we reverse the current node’s pointer. We then reverse the current node’s pointer by setting its next pointer to point to the prev node. Finally, we move both prev and current pointers one node ahead by setting prev to point to the current node, and current to point to the next_node node.
After the loop ends, the prev pointer will be pointing to the new head of the reversed list, and we can print its value or perform any other operation we want on it.
You can leverage similar logic to reverse a doubly linked list.
How do you check if a linked list is circular?
To check if a linked list is circular, we can use the two-pointer technique, which is also known as the “slow and fast pointer” approach. We start with two pointers, slow_ptr and fast_ptr, both pointing to the head of the linked list. We then move the pointers through the list, with the slow_ptr moving one node at a time, and the fast_ptr moving two nodes at a time.
If the linked list is not circular, then the fast_ptr will eventually reach the end of the list (i.e., it will become null), and we can return false. However, if the linked list is circular, then the fast_ptr will eventually catch up to the slow_ptr, meaning that they will both be pointing to the same node at the same time. At this point, we can return true.
Here is an example of how to do this in pseudocode:
slow_ptr = head
fast_ptr = head
while fast_ptr is not null and fast_ptr.next is not null:
// Move the slow pointer one node at a time
slow_ptr = slow_ptr.next
// Move the fast pointer two nodes at a time
fast_ptr = fast_ptr.next.next
// If the fast pointer catches up to the slow pointer, then the list is circular
if slow_ptr == fast_ptr:
return true
// If we reach the end of the list without finding a cycle, then it is not circular
return false
In this code, we start with two pointers, slow_ptr and fast_ptr, both pointing to the head of the linked list. We then enter a loop that continues as long as fast_ptr is not null and fast_ptr.next is not null (indicating that we have not reached the end of the list yet).
Inside the loop, we move the slow pointer one node at a time by setting slow_ptr to point to the next node in the list. We also move the fast pointer two nodes at a time by setting fast_ptr to point to the next.next node in the list.
If the fast_ptr catches up to the slow_ptr, then we have found a cycle in the linked list, and we can return true. Otherwise, we continue iterating through the list until we reach the end, at which point we can return false because we have not found a cycle.
How do you delete a node in a linked list given only a pointer to that node?
To delete a node in a linked list given only a pointer to that node (i.e., we do not have a pointer to the previous node), we can simply copy the value of the next node into the current node, and then delete the next node. This effectively removes the current node from the linked list, as the next node now takes its place.
Here is an example of how to do this in pseudocode:
if node_to_delete is null or node_to_delete.next is null:
// Cannot delete the last node or a null node
return
// Copy the value of the next node into the current node
node_to_delete.value = node_to_delete.next.value
// Delete the next node
node_to_delete.next = node_to_delete.next.next
In this code, we first check if the node_to_delete is null or the last node in the linked list (i.e., it has no next node). In either of these cases, we cannot delete the node, so we simply return without doing anything.
If the node_to_delete is valid, we copy the value of the next node into the current node, effectively overwriting the current node’s value with the next node’s value. We then delete the next node by setting the next pointer of the current node to point to the next.next node, effectively bypassing the next node and removing it from the linked list.
After this operation, the node_to_delete has effectively been removed from the linked list, and we can continue with any other operations we need to perform on the modified linked list.
How do you find the nth node from the end of a linked list?
To find the nth node from the end of a linked list, we can use the two-pointer technique, which is also known as the “slow and fast pointer” approach. We start with two pointers, slow_ptr and fast_ptr, both pointing to the head of the linked list. We then move the fast_ptr ahead by n nodes, so that it is n nodes ahead of the slow_ptr.
We then move both pointers forward one node at a time until the fast_ptr reaches the end of the linked list. At this point, the slow_ptr will be pointing to the nth node from the end of the linked list.
Here is an example of how to do this in pseudocode:
slow_ptr = head
fast_ptr = head
// Move the fast pointer n nodes ahead
for i in range(n):
if fast_ptr is null:
// The linked list is too short to have an nth node from the end
return null
fast_ptr = fast_ptr.next
// Move both pointers one node at a time until the fast pointer reaches the end
while fast_ptr is not null:
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next
// At this point, the slow pointer is pointing to the nth node from the end
return slow_ptr
In this code, we start with two pointers, slow_ptr and fast_ptr, both pointing to the head of the linked list. We then move the fast_ptr ahead by n nodes using a loop that runs n times. If the fast_ptr becomes null before we have moved it n nodes ahead, then the linked list is too short to have an nth node from the end, so we return null.
Once the fast_ptr is n nodes ahead of the slow_ptr, we enter a loop that moves both pointers forward one node at a time until the fast_ptr reaches the end of the linked list. At this point, the slow_ptr will be pointing to the nth node from the end, so we can return it or perform any other operation we want on it.
How do you detect if there is a loop in a linked list?
To detect if there is a loop in a linked list, we can use the two-pointer technique, which is also known as the “slow and fast pointer” approach. We start with two pointers, slow_ptr and fast_ptr, both pointing to the head of the linked list. We then move the pointers through the list, with the slow_ptr moving one node at a time, and the fast_ptr moving two nodes at a time.
If the linked list has a loop, then the fast_ptr will eventually catch up to the slow_ptr, meaning that they will both be pointing to the same node at the same time. At this point, we can return true to indicate that a loop exists. However, if the linked list does not have a loop, then the fast_ptr will eventually reach the end of the list (i.e., it will become null), and we can return false.
Here is an example of how to do this in pseudocode:
slow_ptr = head
fast_ptr = head
while fast_ptr is not null and fast_ptr.next is not null:
// Move the slow pointer one node at a time
slow_ptr = slow_ptr.next
// Move the fast pointer two nodes at a time
fast_ptr = fast_ptr.next.next
// If the fast pointer catches up to the slow pointer, then there is a loop
if slow_ptr == fast_ptr:
return true
// If we reach the end of the list without finding a cycle, then there is no loop
return false
In this code, we start with two pointers, slow_ptr and fast_ptr, both pointing to the head of the linked list. We then enter a loop that continues as long as fast_ptr is not null and fast_ptr.next is not null (indicating that we have not reached the end of the list yet).
Inside the loop, we move the slow pointer one node at a time by setting slow_ptr to point to the next node in the list. We also move the fast pointer two nodes at a time by setting fast_ptr to point to the next.next node in the list.
If the fast_ptr catches up to the slow_ptr, then we have found a cycle in the linked list, and we can return true. Otherwise, we continue iterating through the list until we reach the end, at which point we can return false because we have not found a cycle.
How do you sort a linked list?
There are several ways to sort a linked list, but one of the most efficient algorithms is Merge Sort. Here is an example of how to implement Merge Sort on a linked list:
- Divide the list into two halves using the slow and fast pointer approach.
- Recursively sort the two halves of the linked list.
- Merge the two sorted halves back together to produce the final sorted list.
Here is an example of how to do this in pseudocode:
function merge_sort(head):
// Base case: if the list is empty or has only one node, it is already sorted
if head is null or head.next is null:
return head
// Divide the list into two halves using the slow and fast pointer approach
slow_ptr = head
fast_ptr = head.next
while fast_ptr is not null and fast_ptr.next is not null:
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next.next
// Recursively sort the two halves of the linked list
second_half_head = slow_ptr.next
slow_ptr.next = null
first_half = merge_sort(head)
second_half = merge_sort(second_half_head)
// Merge the two sorted halves back together
return merge(first_half, second_half)
function merge(first, second):
if first is null:
return second
if second is null:
return first
if first.value <= second.value:
merged_head = first
merged_head.next = merge(first.next, second)
else:
merged_head = second
merged_head.next = merge(first, second.next)
return merged_head
In this code, the merge_sort function sorts the linked list by dividing it into two halves using the slow and fast pointer approach, recursively sorting the two halves, and then merging them back together using the merge function.
The merge function takes two sorted linked lists as input and merges them together into a single sorted linked list. It does this by comparing the values of the first nodes in each list and creating a new node that points to the smaller of the two nodes. It then recursively calls itself to merge the remaining nodes in the two lists.
After the merge_sort function completes, it returns the head of the final sorted linked list. We can then iterate through the list and perform any other operations we need to on the sorted list.
How do you merge two sorted linked lists into a single sorted linked list?
To merge two sorted linked lists into a single sorted linked list, we can create a new linked list and iteratively compare the nodes of the two input lists, appending the smaller node to the end of the output list. Once one of the input lists has been fully processed, we can simply append the remaining nodes from the other list to the end of the output list.
Here is an example of how to do this in pseudocode:
function merge_sorted_lists(head1, head2):
// Create a new linked list to store the merged output
merged_head = null
current_node = null
// Traverse the two input lists and compare their nodes
while head1 is not null and head2 is not null:
if head1.value <= head2.value:
// Append the node from the first list to the output list
if merged_head is null:
merged_head = head1
current_node = head1
else:
current_node.next = head1
current_node = current_node.next
head1 = head1.next
else:
// Append the node from the second list to the output list
if merged_head is null:
merged_head = head2
current_node = head2
else:
current_node.next = head2
current_node = current_node.next
head2 = head2.next
// Append any remaining nodes from the first list to the output list
if head1 is not null:
if merged_head is null:
merged_head = head1
else:
current_node.next = head1
// Append any remaining nodes from the second list to the output list
if head2 is not null:
if merged_head is null:
merged_head = head2
else:
current_node.next = head2
return merged_head
In this code, we start by creating a new linked list to store the merged output, with merged_head and current_node both initially set to null. We then iterate through the two input lists using a loop that compares the nodes of the two lists and appends the smaller node to the output list. Once one of the input lists has been fully processed, we simply append the remaining nodes from the other list to the output list.
After the loop ends, we check if there are any remaining nodes in either of the input lists and append them to the end of the output list if necessary. Finally, we return the head of the merged output list.
