## Print binary tree in level order

Question 17. Print the nodes of a binary tree in level order

To print the nodes of the binary tree in level order, we start with the root node and then print the child nodes in each level from left to right. Consider the binary tree below The level order printing will result in the following output: ABCDEFG. To achieve this we make use of a queue and use the following strategy:

1. Add the root node to the queue

2. Remove the head element of the queue and print it. Then add the children of the removed element back to the queue. Repeat step-2 till the queue becomes empty. ## C/C++

```
/*
root: root node of the tree
q: queue that helps in printing in level order
*/
void print_level_order(struct node *root, queue<struct node*>& q)
{
struct node *n;
int num_nodes_in_cur_level, num_nodes_in_next_level;

if (!root)
return;

/*Add the root node to the empty queue*/
q.push(root);
num_nodes_in_cur_level = 1;
num_nodes_in_next_level = 0;

/*Process the nodes in the queue in Breadth First manner*/
while (!q.empty()) {

/*Remove the node at the head of the queue*/
n = q.front();
q.pop();

print_data(n->data); /*print the data in the node*/

/*Add the left child to the end of the queue*/
if (n->left) {
q.push(n->left);
num_nodes_in_next_level++;
}

/*Add the right child to the end of the queue*/
if (n->right) {
q.push(n->right);
num_nodes_in_next_level++;
}

num_nodes_in_cur_level--;

/*go to next line, if all nodes in current level are processed*/
if (num_nodes_in_cur_level == 0) {
cout << endl;
num_nodes_in_cur_level = num_nodes_in_next_level;
num_nodes_in_next_level = 0;
}
}
}

```

## Java

```
/*
root: root node of the tree
q: queue used for printing the tree
*/
public static void printLevelOrder(TreeNode root, Queue<TreeNode> q) {
if (root == null)
return;

/*Add the root node to the empty queue*/
int numNodesInCurLevel = 1;
int numNodesInNextLevel = 0;

/*Process the nodes in the queue in Breadth First manner*/
while (!q.isEmpty()) {

/*Remove the node at the head of the queue*/
TreeNode n = q.remove();

printData(n.data); /*print the data in the node*/

/*Add the left child to the queue*/
if (n.left != null) {
numNodesInNextLevel++;
}

/*Add the right child to the queue*/
if (n.right != null) {
numNodesInNextLevel++;
}

numNodesInCurLevel--;

/*go to next line, if all nodes in current level are processed*/
if (numNodesInCurLevel == 0) {
System.out.println();
numNodesInCurLevel = numNodesInNextLevel;
numNodesInNextLevel = 0;
}
}
}

```

## Python

```
#root: root node of the tree
#q: Python Queue object used for printing the tree
@staticmethod
def print_level_order(root, q):
if (not root):
return

#Add the root node to the empty queue
q.put(root)
num_nodes_in_cur_level = 1
num_nodes_in_next_level = 0

#Process the nodes in the queue in Breadth First manner
while (not q.empty()) :
#Remove the node at the head of the queue
n = q.get()

TreeNode.print_data(n.data) #print the data in the node

#Add the left child to the queue
if (n.left) :
q.put(n.left)
num_nodes_in_next_level += 1

#Add the right child to the queue
if (n.right) :
q.put(n.right)
num_nodes_in_next_level += 1

num_nodes_in_cur_level = num_nodes_in_cur_level - 1

#go to next line, if all nodes in current level are processed
if (num_nodes_in_cur_level == 0) :
print('')
num_nodes_in_cur_level = num_nodes_in_next_level
num_nodes_in_next_level = 0

```

## Find if a binary tree is a binary search tree

Question 16. Find if a binary tree is a binary search tree The initial approach that comes to mind is to check if the left child node is smaller than the parent node and the right child node is greater than the parent node for all the nodes in the tree. However this solution will not work as shown in the binary tree above. Every node satisfies the condition that the left child is smaller than the parent and the right child is greater than the parent. But the tree is still not a binary search tree since node 9 is incorrect. To correctly find out if a tree is a binary search tree, we should traverse the tree in-order and check if the nodes are present in ascending order

## C/C++

```
/*cur_node: current node whose left and right sub-trees need to be checked
prev_node_pp: the in-order predecessor of cur_node
Return value: 1 if the tree is a binary search tree, 0 otherwise
*/
int is_bst(struct node *cur_node, struct node ** prev_node_pp)
{
if (!cur_node)
return 1;

/*Check if the left sub-tree is a BST*/
if (!is_bst(cur_node->left, prev_node_pp))
return 0;

/*If data in cur_node is <= to previous node then it is not a BST*/
if (*prev_node_pp && cur_node->data <= (*prev_node_pp)->data)
return 0;

/*Update previous node to current node*/
*prev_node_pp = cur_node;

/*Check if the right sub-tree is a BST*/
return is_bst(cur_node->right, prev_node_pp);
}

```

## Java

```
/*curNode: current node
prevNodeArray: in-order predecessor of curNode is present in prevNodeArray
Return value: true if the tree is a binary search tree, false otherwise
*/
public static boolean isBst(TreeNode curNode, TreeNode[] prevNodeArray)  {
if (curNode == null)
return true;

/*Check if the left sub-tree is a BST*/
if (!isBst(curNode.left, prevNodeArray))
return false;

/*If data in curNode is <= previous node then it is not a BST*/
TreeNode prevNode = prevNodeArray;
if (prevNode != null && curNode.data <= prevNode.data)
return false;

/*Update previous node to current node*/
prevNodeArray = curNode;

/*Check if the right sub-tree is a BST*/
return isBst(curNode.right, prevNodeArray);
}

```

## Python

```
#cur_node: current node
#prev_node_list: prev_node_list has in-order predecessor of cur_node
#Return values: True if the tree is a binary search tree, False otherwise
@staticmethod
def is_bst(cur_node, prev_node_list):
if (not cur_node):
return True

#Check if the left sub-tree is a BST
if (not TreeNode.is_bst(cur_node.left, prev_node_list)):
return False

#If data in cur_node is <= previous node then it is not a BST
prev_node = prev_node_list
if (prev_node and cur_node.data <= prev_node.data):
return False

#Update previous node to current node
prev_node_list = cur_node

#Check if the right sub-tree is a BST
return TreeNode.is_bst(cur_node.right, prev_node_list)

```

## Is binary tree balanced

Question 15. Find if a binary tree is balanced

A binary tree is balanced if at every node in the tree, the absolute difference between the height of the left-subtree and the height of the right sub-tree doesn’t exceed 1. To solve the problem we recursively traverse the tree and calculate the height of the nodes in a bottom up manner. If at any node, the difference between the height of the left and right sub-trees exceeds 1, we report that the tree is unbalanced.

## C/C++

```
/*cur_node: node of the binary tree being checked
height: height of the current node is returned here
Return value: 1 if the tree is balanced, 0 otherwise
*/
int is_balanced(struct node *cur_node, int *height)
{
int is_left_balanced, is_right_balanced;
int left_height, right_height;

if (!cur_node) {
*height = 0;
return 1;
}

is_left_balanced = is_balanced(cur_node->left, &left_height);
is_right_balanced = is_balanced(cur_node->right, &right_height);

if (!is_left_balanced || !is_right_balanced)
return 0;

/*If the difference between height of left subtree and height of
right subtree is more than 1, then the tree is unbalanced*/
if (abs(left_height - right_height) > 1)
return 0;

/*To get the height of the current node, we find the maximum of the
left subtree height and the right subtree height and add 1 to it*/
*height = max(left_height, right_height) + 1;

return 1;
}

```

## Java

```
/*curNode: node of the binary tree being checked
height: height of the curNode is returned here
Return value: true if the tree is balanced, false otherwise
*/
public static boolean isBalanced(TreeNode curNode, Int height) {
Int leftHeight = new Int();
Int rightHeight = new Int();

if (curNode == null) {
height.value = 0;
return true;
}

boolean isLeftBalanced = isBalanced(curNode.left, leftHeight);
boolean isRightBalanced = isBalanced(curNode.right, rightHeight);

if (!isLeftBalanced || !isRightBalanced)
return false;

/*If the difference between height of left subtree and height of
right subtree is more than 1, then the tree is unbalanced*/
if (Math.abs(leftHeight.value - rightHeight.value) > 1)
return false;

/*To get the height of the current node, we find the maximum of the
left subtree height and the right subtree height and add 1 to it*/
height.value = Math.max(leftHeight.value, rightHeight.value) + 1;

return true;
}

```

## Python

```
#cur_node: node of the binary tree being checked
#Return values: 1. True if the tree is balanced, False otherwise
#		2. height of the cur_node is also returned
@staticmethod
def is_balanced(cur_node) :
if (not cur_node) :
height = 0
return True, height

is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

#To get the height of the current node, we find the maximum of the
#left subtree height and the right subtree height and add 1 to it
height = max(left_height, right_height) + 1

if (not is_left_balanced or not is_right_balanced):
return False, height

#If the difference between height of left subtree and height of
#right subtree is more than 1, then the tree is unbalanced
if (abs(left_height - right_height) > 1):
return False, height

return True, height

```

## Is binary tree symmetric

Question 14. Find if a binary tree is symmetric

A binary tree is symmetric, if the left sub-tree of each node is a mirror image of the right sub-tree. An example of a symmetric binary tree is given below ## C/C++

```
int compare_nodes ( struct node *n1, struct node *n2) {
if (!n1 && !n2)  /*If both the nodes are NULL */
return 1;  /* return symmetric*/

if ( (n1 && !n2) || (!n1 && n2)) /*If one node is NULL and other is not*/
return 0; /*return not symmetric*/

if (n1->data != n2->data) /*If data of two nodes don't match */
return 0; /* return not symmetric */

if (!compare_nodes (n1->left, n2->right))
return 0;

if (!compare_nodes (n1->right, n2->left))
return 0;

return 1; /*Return symmetric*/
}

/*Returns 1 if the tree is symmetric, 0 otherwise*/
int is_symmetric(struct node * root) {
if (!root)
return 1;

return compare_nodes(root->left, root->right);
}

```

## Java

```
public static boolean compareNodes ( TreeNode n1, TreeNode n2) {
if (n1 == null && n2 == null)  /*If both the nodes are null */
return true;  /* return symmetric*/

/*If one node is null and the other is not null*/
if ( (n1 != null && n2 == null) || (n1 == null && n2 != null))
return false; /*return not symmetric*/

if (n1.data != n2.data) /*If data of two nodes don't match */
return false; /* return not symmetric */

if (!compareNodes (n1.left, n2.right))
return false;

if (!compareNodes (n1.right, n2.left))
return false;

return true; /*Return symmetric*/
}

/*Returns true if the tree is symmetric, false otherwise*/
public static boolean isSymmetric(TreeNode root) {
if (root == null)
return true;

return compareNodes(root.left, root.right);
}

```

## Python

```
@staticmethod
def compare_nodes(n1, n2):
if (not n1 and not n2):  #If both the nodes are None
return True  # return symmetric

#If one node is None and the other is not None
if ( (n1 and not n2) or (not n1 and n2)):
return False #return not symmetric

if (n1.data != n2.data): #If data of two nodes don't match
return False # return not symmetric

if (not TreeNode.compare_nodes(n1.left, n2.right)):
return False

if (not TreeNode.compare_nodes(n1.right, n2.left)):
return False

return True #Return symmetric

@staticmethod
#Returns True if the tree is symmetric, False otherwise
def is_symmetric(root):
if (not root):
return True

return TreeNode.compare_nodes(root.left, root.right)

```

## Mirror image of a binary tree

Question 13. Convert a binary tree into its mirror image

An example of a binary tree and its mirror image is shown below. So to convert the binary tree to its mirror image, the left child and the right child of each node in the tree should be swapped

## C/C++

```
/*
cur_node: current node of the tree whose mirror image should be computed
*/
void compute_mirror_image(struct node *cur_node) {
struct node *temp_node;

if (cur_node) {
/*Swap the left child and right child of the current node*/
temp_node = cur_node->left;
cur_node->left = cur_node->right;
cur_node->right = temp_node;

/*Recursively compute the mirror image */
compute_mirror_image(cur_node->left);
compute_mirror_image(cur_node->right);
}
}

```

## Java

```
/*
curNode: current node of the tree whose mirror image should be computed
*/
public static void computeMirrorImage(TreeNode curNode) {
if (curNode != null) {
/*Swap the left child and right child of the current node*/
TreeNode tempNode = curNode.left;
curNode.left = curNode.right;
curNode.right = tempNode;

/*Recursively compute the mirror image */
computeMirrorImage(curNode.left);
computeMirrorImage(curNode.right);
}
}

```

## Python

```
@staticmethod
#cur_node: current node of the tree whose mirror image should be computed
def compute_mirror_image(cur_node):
if (cur_node) :
#Swap the left child and right child of the current node
cur_node.left, cur_node.right = cur_node.right, cur_node.left

#Recursively compute the mirror image
TreeNode.compute_mirror_image(cur_node.left)
TreeNode.compute_mirror_image(cur_node.right)

```

## Stack using queues

Question 12. Implement a stack using queues

To implement a stack using queues, we have to perform the push and pop operations of the stack using the enqueue and dequeue operations supported by the queues.

A stack can be implemented using two internal queues Q1 and Q2. There are two ways to achieve this: one where the push operation is more efficient than the pop operation and the other where the pop operation is more efficient than the push operation.

Case 1: Push is more efficient than pop
When an element is pushed to the stack, the element is enqueued in Q1

When an element is popped from the stack, dequeue the first N-1 elements from Q1 (N is the number of elements currently present in Q1) and enqueue them in Q2, one element at a time. Dequeue the last element from Q1 and return it as the element popped from the stack. Now rename Q1 as Q2 and Q2 as Q1.

For instance, let us say that the elements A, B and C are added to the stack. Then A, B, C will be enqueued into Q1 as shown in the diagram below Now if an element must be popped from the stack, dequeue A and B from Q1, then enqueue A and B in Q2. Finally dequeue the last element in Q1 which is C and return it as the popped element. Once this is done, the state of Q1 and Q2 are shown below In the last step of the pop operation, Q1 is renamed as Q2 and Q2 is renamed as Q1 as shown below The code for implementing a stack class using queues where push is efficient is given below

## C/C++

```
template <class T> class StackUsingQueues
{
private:
queue<T> *q1;
queue<T> *q2;

public:
StackUsingQueues() {
q1 = new queue<T>();
q2 = new queue<T>();
}

~StackUsingQueues() {
delete q1;
delete q2;
}

bool empty() {
/*Stack is empty only if both queues are empty*/
if (q1->empty() && q2->empty())
return true;

return false;
}

void push(T new_element) {
/*Add element to the end of queue q1*/
q1->push(new_element);
}

T pop() {
/*If stack is empty, then throw an exception*/
if (empty())
throw exception();

T e;
/*Remove all elements from q1 and add it to q2 except the last item*/
while (q1->size() > 1) {
e = q1->front();
q1->pop();
q2->push(e);
}

/*Remove the last element in q1. It will contain the top of stack*/
e = q1->front();
q1->pop();

/*Swap the queues q1 and q2*/
queue<T> *temp = q1;
q1 = q2;
q2 = temp;

return e; /*Return the top of the stack*/
}

};

```

## Java

```
class StackUsingQueues <T> {
private Queue<T> q1;
private Queue<T> q2;

public StackUsingQueues () {
}

public boolean isEmpty() {
/*Stack is empty if q1 is empty*/
if (q1.isEmpty())
return true;
return false;
}

public void push(T newElement) {
/*Add elements only to queue q1*/
}

public T pop() {
if (isEmpty())
return null;

/*Remove all elements from q1 and add it to q2 except the last item*/
T e;
while (q1.size() > 1) {
e = q1.remove();
}

/*Remove the last element in q1. It will contain the top of stack*/
e = q1.remove();

/*Swap q1 and q2*/
Queue<T> temp = q1;
q1 = q2;
q2 = temp;

return e; /*Return the top of the stack*/
}

}

```

## Python

```
#Queue in Python 2.7 has been renamed to queue. So handling this so that code
#is portable on all versions of Python
try:
import queue
except ImportError:
import Queue as queue

class StackUsingQueues(object):
def __init__(self):
#Create the internal queues
self.q1 = queue.Queue()
self.q2 = queue.Queue()

def empty(self):
#Stack is empty if q1 is empty
if (self.q1.empty()):
return True
return False

def push(self, new_element):
#Add elements only to queue q1
self.q1.put(new_element)

def pop(self):
if (self.q1.empty()):
return None

#Remove all elements from q1 and add it to q2 except the last item
while (self.q1.qsize() > 1):
e = self.q1.get()
self.q2.put(e)

#Remove the last element in q1. It will contain the top of stack
e = self.q1.get()

#Swap q1 and q2
self.q1, self.q2 = self.q2, self.q1

return e #Return the top of the stack

```

Case 2: Pop is more efficient than push

When an element is pushed to the stack, the element is enqueued in Q1. All the elements of Q2 are dequeued and enqueued in Q1. Rename Q1 as Q2 and Q2 as Q1. So Q2 will always contain elements in the reverse order of insertion.
When an element is popped from the stack, a dequeue operation is performed on Q2 to obtain the element at the top of the stack.

## Queue using stacks

Question 11. Implement a queue using stacks

To implement a queue using stacks, we have to perform the enqueue and dequeue operations of the queue using the push and pop operations supported by the stacks.

Let us say that we internally use stack S1 to implement a queue. When elements are added to the queue, they are pushed onto the internal stack S1. However when we have to remove an element from the queue, if we pop the element from S1, we will be returning the most recently added element instead of the element first added to the queue. We solve this problem by using an additional internal stack S2 that stores the elements to be removed from the queue in correct order. So S2 should store the elements in reverse order of S1. By popping each element from S1 and immediately pushing it into S2, S2 will store the elements in reverse order of S1. To remove an element from the queue, we will have to just pop the element from S2.

For instance, let us say that elements A, B and C are added to the queue. Then S1 will contain A, B and C while S2 will be empty as shown in the diagram below. Now if an element has to be removed from the queue, since S2 is empty, each element of S1 is popped and immediately pushed into S2 as shown in the diagram below. The top of stack S2 (which is element A) is then popped to remove the element from the queue.

It is important to note that, elements should be popped from S1 and pushed into S2 only when S2 is completely empty. For instance, after A is removed, let the element D be added to the queue. D is first added to S1. Suppose D is popped from S1 and pushed to S2 even before S2 is empty, then the state of the stacks is shown below Clearly this results in an incorrect behavior since the next element that will be removed from the queue is D as D is at the top of S2 whereas the correct element to be removed from the queue is the element B. The code for a queue class using stacks is given below:

## C/C++

```
template <class T> class QueueUsingStacks
{
private:
stack<T> s1;
stack<T> s2;

public:
QueueUsingStacks() {

}

/*Add elements only to stack s1*/
s1.push(new_element);
}

T remove() {
T e;
if(s2.empty()) {
/*We remove elements only from stack s2. So
if s2 is empty, then pop all the elements from s1 and
push them into s2.*/
while(!s1.empty()) {
e = s1.top();
s1.pop();
s2.push(e);
}
}

if (s2.empty())
throw exception();

/*If s2 is not empty, then remove the element from top of s2.
This element corresponds to the head of the queue*/
e = s2.top();
s2.pop();
return e;
}

bool empty() {
/*Queue is empty only if both stacks are empty*/
if (s1.empty() && s2.empty())
return true;
return false;
}

};

```

## Java

```
class QueueUsingStacks <T> {
private Stack<T> s1;
private Stack<T> s2;

public QueueUsingStacks () {
s1 = new Stack<T>();
s2 = new Stack<T>();
}

/*Add elements only to stack s1*/
s1.push(newElement);
}

public T remove() {
T e;
if(s2.isEmpty()) {
/*We remove elements only from stack s2. So
if s2 is empty, then pop all the elements from s1 and
push them into s2.*/
while(!s1.isEmpty()) {
e = s1.pop();
s2.push(e);
}
}

/*If s2 is not empty, then remove the element from top of s2.
This element corresponds to the head of the queue*/
e = null;
if(!s2.isEmpty())
e = s2.pop();

return e;
}

public boolean isEmpty() {
/*Queue is empty only if both stacks are empty*/
if (s1.isEmpty() && s2.isEmpty())
return true;
return false;
}

}

```

## Python

```
#Queue in Python 2.7 has been renamed to queue. So handling this so that code
#is portable on all versions of Python
try:
import queue
except ImportError:
import Queue as queue

class QueueUsingStacks(object):
def __init__(self):
#Create the internal stacks
self.s1 = queue.LifoQueue()
self.s2 = queue.LifoQueue()

#Add elements only to stack s1
self.s1.put(new_element)

def remove(self):
if(self.s2.empty()) :
#We remove elements only from stack s2. So
#if s2 is empty, then pop all the elements from s1 and
#push them into s2.
while(not self.s1.empty()) :
e = self.s1.get()
self.s2.put(e)

#If s2 is not empty, then remove the element from top of s2.
#This element corresponds to the head of the queue
e = None
if(not self.s2.empty()):
e = self.s2.get()

return e

def empty(self):
#Queue is empty only if both stacks are empty
if (self.s1.empty() and self.s2.empty()):
return True
return False

```

Question 10. Interleave two linked lists

Let’s consider two linked lists, L1 having the members A->B->C->D and L2 having the members X->Y->Z. Interleaving the two linked lists will result in the single linked list A->X->B->Y->C->Z->D, wherein the first node of L2 is placed next to the first node of L1, second node of L2 is placed next to second node of L1 and so on. If the sizes of the two linked lists are m and n, then interleaving can be done in O(m+n)

## C/C++

```
/*
*/
struct node* interleave_lists( struct node *n1, struct node *n2)
{
struct node *result,  *temp1, *temp2;

if (!n1) {
return n2; /*If linked list1 is empty, return n2 */
}

if (!n2) {
return n1; /*If linked list2 is empty, return n1*/
}

result = n1;
while (n1 != NULL && n2 != NULL) {
temp1 = n1->next;
temp2 = n2->next;

/*Place node of second linked list next to the node
if (n1->next)
n2->next = n1->next;
n1->next = n2;

n1 = temp1;
n2 = temp2;
}
return result;
}

```

## Java

```
/*
*/

if (n1 == null) {
return n2; /*If linked list1 is empty, return n2 */
}

if (n2 == null) {
return n1; /*If linked list2 is empty, return n1*/
}

while (n1 != null && n2 != null) {

/*Place node of second linked list next to the node
if (n1.next != null)
n2.next = n1.next;
n1.next = n2;

n1 = temp1;
n2 = temp2;
}
return result;
}

```

## Python

```
@staticmethod
def interleave(n1, n2):
if (not n1):
return n2 #If linked list1 is empty, return n2

if (not n2):
return n1 #If linked list2 is empty, return n1

result = n1
while (n1 and n2):
temp1 = n1.next
temp2 = n2.next

#Place node of second linked list next to the node of
if (n1.next):
n2.next = n1.next

n1.next = n2

n1 = temp1
n2 = temp2

return result

```

## Find cycle in Linked List

Question 9. Find out if there is a cycle in a linked list. Also find the node where the cycle begins

We can maintain the is_visited field in each node. Initially the is_visited field in all the nodes is set to 0. When a node is traversed in the linked list, the is_visited field is changed from 0 to 1. While traversing the linked list, the moment we encounter a node whose is_visited field is already 1, we know that there is a cycle in the linked list and the cycle begins at this node. The drawback of this approach is that it uses additional memory.

To solve the problem without using additional memory, we use the following idea. Suppose two runners take part in a race, one of them being faster than the other, the faster runner will overtake the slower runner as soon as the race starts. If the race track is a loop, then later in the race, the faster runner will again meet the slower runner and overtake him. Similarly, we can traverse the linked list using a fast pointer and a slow pointer. At each step, the fast pointer is moved ahead by 2 nodes, whereas the slow pointer is moved ahead by 1 node. If there is a loop in the linked list, the two pointers will meet at a common node.

To find where the loop starts, we need to do the following: Let n1 be the fast pointer and n2 be the slow pointer. When n1 and n2 meet, initialize a third pointer n3 to point to the beginning of the linked list. So n1 is ahead of n3 in the linked list. Now ignore n2 and advance n1 and n3 one node at a time. The node where n1 and n3 meet is where the loop starts.

## C/C++

```/*head: first node of the linked list
Return value: first node in loop if loop exists, NULL otherwise
*/
struct node* find_loop( struct node *head)
{
int found_loop = 0;

/*n1 is the fast pointer. So advance it by two steps
n2 is slow pointer. So advance it by one step
*/
while (n1 != NULL) {
n1 = n1->next;
if (n1) {
n1 = n1->next;
n2 = n2->next;
}

/*If n1 and n2 meet then there is a loop in the linked list*/
if (n1 == n2) {
found_loop = 1;
break;
}
}

if (!found_loop)
return NULL;

/*Find the beginning of the loop*/
while (n1 != n3) {
n1 = n1->next;
n3 = n3->next;
}

return n1;
}

```

## Java

```
Return value: first node in loop if loop exists, null otherwise
*/
boolean foundLoop = false;

/*n1 moves fast. So advance it by two steps
n2 is slow. So advance it by one step
*/
while (n1 != null) {
n1 = n1.next;
if (n1 != null) {
n1 = n1.next;
n2 = n2.next;
}

/*If n1 and n2 meet then there is a loop in the linked list*/
if (n1 == n2) {
foundLoop = true;
break;
}
}

if (!foundLoop)
return null;

/*Find the beginning of the loop*/
while (n1 != n3) {
n1 = n1.next;
n3 = n3.next;
}

return n1;
}

```

## Python

```
#Return value: first node in loop if loop exists, None otherwise
@staticmethod
found_loop = False

#n1 moves fast. So advance it by two steps
#n2 is slow. So advance it by one step
while (n1):
n1 = n1.next
if (n1):
n1 = n1.next
n2 = n2.next

#If n1 and n2 meet then there is a loop in the linked list
if (n1 == n2):
found_loop = True
break

return None

#Find the beginning of the loop
while (n1 != n3):
n1 = n1.next
n3 = n3.next

return n1

```

## Find where two linked lists merge

Question 8. Two linked lists merge at a common node. Given the heads of the two linked lists, find the node where the linked lists merge. For instance, the two linked lists ABCXYZ and PQXYZ merge at node X

Using a brute force approach, we can pick each node in the first linked list and compare it with every node in the second linked list in sequential order. If we get a match, then we have found the first common node between the two linked lists. If one linked list has m nodes and the other has n nodes, this takes O(mn) time.
However there are better techniques to solve the problem. Two approaches which can perform better than the brute force approach are described below

Approach 1: Marking the nodes
An extra field is maintained in each node to indicate if the node has been visited or not. Initially the nodes in both linked lists have the field set to 0 indicating that they have not yet been visited. The nodes of the first linked list are then traversed and the visited field in the first linked list nodes is set to 1 indicating that they have been visited. Then the nodes of the second linked list are traversed in sequential order. As soon as we encounter a node in the second linked list with the visited field set to 1, we have found the first node that is common to both the linked lists. The time taken by this approach is O(m+n) and it requires additional space in each node to store the visited field

Approach 2: Counting

## C/C++

```
/*
Return value: first common node between the two linked lists
*/
{
struct node *n1, *n2;
int length1, length2, diff;

/*Find the length of the two linked lists*/

if (length1 >= length2) {
} else {
}

/*Find the difference in length of the two linked lists. Then advance
n1 by the difference*/
diff = abs(length1 - length2);
while (diff > 0) {
n1 = n1->next;
--diff;
}

/*Go on comparing the nodes in linked list1 starting from n1 and
linked list2 starting from n2 till n1 and n2 match*/
while (n1 && n2 && n1 != n2) {
n1 = n1->next;
n2 = n2->next;
}

/*n1 will have the common node if it exists, otherwise n1 will be NULL*/
return n1;
}

```

## Java

```
/*
Return value: first common node between the two linked lists
*/
/*Find the length of the two linked lists*/

if (length1 >= length2) {
} else {
}

/*Find the difference in length of the two linked lists. Then advance
n1 by the difference*/
int diff = Math.abs(length1 - length2);
while (diff > 0) {
n1 = n1.next;
--diff;
}

/*Go on comparing the nodes in linked list1 starting from n1 and
linked list2 starting from n2 till n1 and n2 match*/
while (n1 != null && n2 != null && n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}

/*n1 will have the common node if it exists, otherwise n1 will be null*/
return n1;
}

```

## Python

```
#Return value: first common node between the two linked lists
@staticmethod
#Find the length of the two linked lists

if (length1 >= length2) :
else :

#Find the difference in length of the two linked lists. Then advance
#n1 by the difference
diff = abs(length1 - length2)
while (diff > 0) :
n1 = n1.next
diff = diff - 1

#Go on comparing the nodes in linked list1 starting from n1 and
#linked list2 starting from n2 until n1 and n2 match
while (n1 and n2 and n1 != n2) :
n1 = n1.next
n2 = n2.next

#n1 will have the common node if it exists, otherwise n1 will be None
return n1

```