Head and Tail Pointers : Pattern for Coding Interviews

Hack the coding interviews at FAANG!

Unlike arrays there’s no built-in linked list structure in programming languages. However, knowledge about linked lists can be very useful in coding interviews!

Structure of a Singly Linked List

This story requires you to have at least a rudimentary knowledge of linked lists.

Here’s a commonly asked question during coding interviews at FAANG.

Problem Statement : Given two sorted linked lists, merge them so that the resulting linked list is also sorted.

Example :

Input
List 1:  4 -> 8 -> 15 -> 19
List 2:  7 -> 9 -> 10 -> 16 
Output: 4 -> 7 -> 8 -> 9 -> 10 -> 15 -> 16 -> 19

Input (two lists)

Output (merged list)

Solution

We maintain a head and a tail pointer on the merged linked list.

Initially, the merged linked list is NULL. We choose the head of the merged linked list by comparing the first node of both linked lists.

Since it’s the first and only node in the merged list, it will also be the tail of the merged list at this point (initially).

For all subsequent nodes in both lists, we choose the smaller current node and link it to the tail of the merged list; move the current pointer of that list one step forward and also update the tail pointer of the merged list.

We keep doing this while there are some remaining elements in both the lists. If there are still some elements in only one of the lists, we link this remaining list to the tail of the merged list. Now we have the desired merged list.

Here’s a visual representation of the algorithm for another example below:

Value of head1 (4) is less than value of head2 (7), we’ll add 4 to merged tail.

Value of head2, i.e., 7 is smaller than data of head1, i.e., 8. So we add a node with 7 value to the tail of the merged list.

Comparing 8 and 9 as heads in the two lists now, we’ll add 8 to merged list. Will repeat the same process until all the nodes of at least one of the lists have been iterated over and hence appended to the merged list , as shown below

Only the first linked list is left so we point the tail towards the entire first list (head1).

Code (JavaScript):

function mergeSorted(head1, head2) {
// if both lists are empty then merged list is also empty
// if one of the lists is empty then the other one is the desired merged list
if (!head1) {
return head2;
} else if (!head2) {
return head1;
}
//storing the head of the merged list
let mergedHead = null;
if (head1.data <= head2.data) {
mergedHead = head1;
head1 = head1.next;    // updating the list head
} else {
mergedHead = head2;
head2 = head2.next;       // updating the list head
}
let mergedTail = mergedHead;  // initially tail is same as the head
while (head1 && head2) {
let temp = null;  // for storing the smaller of the two nodes
if (head1.data <= head2.data) {
temp = head1;
head1 = head1.next;   // updating the list head
} else {
temp = head2;
head2 = head2.next;   // updating the list head
}
mergedTail.next = temp;  // appending the smaller node to the tail
mergedTail = mergedTail.next;  // updating the tail of merged list
}
//if one of the lists is done with, we need to append the remaining list nodes to the tail of the merged list
if (head1) {
mergedTail.next = head1;  
} else if (head2) {
mergedTail.next = head2;  
}
return mergedHead;  // returning the required merged list
};

Runtime complexity: The runtime complexity of this algorithm is O(n+m) where m and n are the lengths the given linked lists, respectively. We are iterating over each node present in the two lists.

Memory complexity : The memory complexity of this solution is linear, O(n+m), since we are making use of a new list to store all the nodes present in the two lists.

Will cover more coding questions in the upcoming stories.