# 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 :

InputList 1: 4 -> 8 -> 15 -> 19

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

# 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:

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

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 listif (!head1) {return head2;} else if (!head2) {return head1;}//storing the head of the merged listlet 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 headwhile (head1 && head2) {let temp = null; // for storing the smaller of the two nodesif (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 tailmergedTail = 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 listif (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.