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

```

Question 7. Rotate a linked list by k positions

Consider the linked list A->B->C->D->E. If we rotate the linked list by k = 2 positions, then the linked list will become D->E->A->B->C. To perform the rotation we do the following:

1. Locate the kth node from the end (let’s call this node the pivot). If k = 2, we have to locate the second last node which in this case is D.

2. Make the node previous to the pivot point to NULL. So in this case C will point to NULL.

3. Traverse till the end of the linked list and make the last node point to the head of the linked list. So the last node E will point to the head A.

4. Make the pivot the head of the new linked list. So D will now become the new head.

Note that if k = length of linked list, then after rotation we end up with the original linked list. So we apply the formula, k = k % length to figure out the actual rotation required.

## C/C++

```
/*
k: by how many positions the linked list should be rotated
length: number of nodes in the linked list
Return value: first node of the rotated linked list
*/
struct node* rotate_list(struct node *head, int k, int length)
{
struct node *pivot, *prev, *last;

/*If there are 0 or 1 nodes in the linked list, then simply return*/
if (length < 2)

/*If we shift by k times, then we get back the same linked list. So we
just have to shift k % length times*/
k = k % length;

/*If k is 0, then no need to shift*/
if (k == 0)

/*Find the kth node from the end. If k = 1, then pivot will have
the last node and prev will be the node previous to last node*/
prev = NULL;
pivot = find_kth_node_from_end(head, k, length, &prev);

/*Find the last node in the linked list*/
last = pivot;
while (last->next)
last = last->next;

/*Make the last node point to head and the node previous to pivot
point to NULL*/
prev->next = NULL;

/*pivot will be the new head*/
return pivot;
}

```

## Java

```
/*
k: by how many positions the linked list should be rotated
length: number of nodes in the linked list
Return value: first node of the rotated linked list
*/

/*If there are 0 or 1 nodes in the linked list, then simply return*/
if (length < 2)

/*If we shift by k times, then we get back the same linked list. So we
just have to shift k % length times*/
k = k % length;

/*If k is 0, then no need to shift*/
if (k == 0)

/*Find the kth node from the end. If k = 1, then pivot will have
the last node and prev will be the node previous to last node*/

/*Find the last node in the linked list*/
while (last.next != null)
last = last.next;

/*Make the last node point to head and the node previous to pivot
point to null*/
prev.next = null;

/*pivot will be the new head*/
return pivot;
}

```

## Python

```
#k: by how many positions the linked list should be rotated
#length: number of nodes in the linked list
#Return value: first node of the rotated linked list
@staticmethod
#If there are 0 or 1 nodes in the linked list, then simply return
if (length < 2):

#If we shift by k times, then we get back the same linked list.
#So we just have to shift k % length times
k = k % length

#If k is 0, then no need to shift
if (k == 0):

#Find the kth node from the end. If k = 1, then pivot will have
#the last node and prev will be the node previous to last node

#Find the last node in the linked list
last = pivot
while (last.next):
last = last.next

#Make the last node point to head and the node previous to pivot
#point to None
prev.next = None

#pivot will be the new head
return pivot

```

## Remove duplicates from linked list

Question 6. Remove duplicates from a linked list

For removing duplicates, we can try two approaches
1. Use brute force. Pick each node (let’s call it current node) in the linked list, then check the nodes that occur after the current node and remove those nodes that are identical to the current node. The time complexity is O(n2). We don’t need additional memory.

2. Use a hash table. As we traverse the linked list, we store the data of the nodes in the hash table. If the data of a node has already been stored in the hash table, then it is a duplicate and we delete the node from the linked list. The time complexity is O(n) but we will use additional memory because of the hash table.
The code for the brute force approach is given below

## C/C++

```
/*
*/
{
struct node *cur_node, *iter_node, *prev_node;

/*If there are 0 or 1 nodes in linked list, then simply return*/
return;

while (cur_node) {
/*Iterate from node after cur_node to the end of the linked list*/
iter_node = cur_node->next;
prev_node = cur_node;

while (iter_node) {
if (cur_node->data == iter_node->data) {
/*iter_node is a duplicate of cur_node. So remove it*/
prev_node->next = iter_node->next;
free(iter_node);
iter_node = prev_node->next;
} else {
prev_node = iter_node;
iter_node = iter_node->next;
}
}

cur_node = cur_node->next;
}
}

```

## Java

```
/*
*/
/*If there are 0 or 1 nodes in linked list, then simply return*/
return;

while (curNode != null) {
/*Iterate from node after curNode to the end of linked list*/

while (iterNode != null) {
if (curNode.data == iterNode.data) {
/*iterNode is a duplicate of curNode.
so remove it*/
prevNode.next = iterNode.next;
iterNode = iterNode.next;
} else {
prevNode = iterNode;
iterNode = iterNode.next;
}
}

curNode = curNode.next;
}
}

```

## Python

```
@staticmethod
#If there are 0 or 1 nodes in linked list, then simply return
return

while (cur_node) :
#Iterate from node after cur_node to the end of the linked list
iter_node = cur_node.next
prev_node = cur_node

while (iter_node) :
if (cur_node.data == iter_node.data) :
#iter_node is a duplicate of cur_node. so
#remove it
prev_node.next = iter_node.next
iter_node = iter_node.next
else :
prev_node = iter_node
iter_node = iter_node.next

cur_node = cur_node.next

```

## Delete node given pointer to it

Question 5. Delete a node in a linked list given only a pointer/reference to that node

Let us say that we are given only a pointer n1 to the node that needs to be deleted. We don’t know the node previous to n1. If we delete the node that n1 points to, then we can’t update the next pointer of the node preceding n1. So we can’t directly delete n1, but we have to employ a trick to do the job.
To solve the problem, let n2 be the pointer to the node next to n1. We copy n2->data into n1->data. We also copy n2->next into n1->next. Now n1 points to a node that is exactly identical to the node pointed by n2. Now instead of deleting n1, we delete n2. This achieves the required result.
This solution will not work if the node being deleted is the last node in the linked list and the last node points to NULL. One possible approach to make this solution work for all nodes in the linked list is to use a circular linked list.

## C/C++

```
/*
n1: pointer to the node to be deleted
Return value: 0 on success, -1 on failure
*/
int delete_node(struct node *n1)
{
struct node *n2;

if (n1->next) {
/*Get the pointer to the next node*/
n2 = n1->next;

/*Copy the contents of the next node into the current node*/
n1->data = n2->data;
n1->next = n2->next;

/*Free the next node*/
free(n2);

/*Return indicating the operation is successful*/
return 0;
}

/*return indicating the operation failed*/
return -1;
}

```

## Java

```
/*
n1: the node to be deleted
Return value: true on success, false on failure
*/
public static boolean deleteNode(LinkedListNode n1) {

if (n1.next != null) {
/*Get the next node*/

/*Copy the contents of the next node into the current node*/
n1.data = n2.data;
n1.next = n2.next;

/*Return indicating the operation is successful*/
return true;
}

/*return indicating the operation failed*/
return false;
}

```

## Python

```
#n1: the node to be deleted
#Return value: True on success, False on failure
@staticmethod
def delete_node(n1):
if (n1.next):
#Get the next node
n2 = n1.next

#Copy the contents of the next node into the current node
n1.data = n2.data
n1.next = n2.next

#Return indicating the operation is successful
return True

#return indicating the operation failed
return False

```

## Swap kth node from beginning and end

Question 4. Swap the kth node from the end with the kth node from the beginning of a linked list

If the length of the linked list is n, then k can take values from 1 to n. We can solve the problem in O(n) using the following steps:
1. Find the kth node from the start of the linked list (k1) and its previous node (prev1).
2. Find the kth node from the end of the linked list (k2) and its previous node (prev2).
3. Swap k1 and k2. While swapping we have to handle three possible cases:
• k1 and k2 are identical. In this case we don’t have to swap
• k1 and k2 are neighbors (either k1->next = k2 or k2->next = k1)
• k1 and k2 are not neighbors

Note that if k is 1, then we have to swap the head of the linked list with the tail of the linked list. In this case, the head of the linked list will change. Also note that the node k1 may lie before or after k2. For instance, if linked list length is 10 and k = 3, then k1 is before k2. But if linked list length is 10 and k = 9, then k1 is after k2

## C/C++

```
/*Helper function which swaps two neighbors n1 and n2
prev: node previous to n1
n1: first node to be swapped
n2: second node to be swapped. n2 occurs immediately after n1
*/
struct node* swap_neighbors(struct node *head, struct node *prev,
struct node *n1, struct node *n2)
{
/*Swap n1 and n2*/
n1->next = n2->next;
n2->next = n1;

if (prev) {
prev->next = n2;
} else {
}
}

/*Main function for swapping the kth node from beginning and end
k: which node in the linked list should be swapped
length: number of nodes in the linked list
Return value: head of the result linked list on success, NULL on error
*/
struct node* swap_kth_node(struct node *head, int k, int length)  {
struct node  *temp;
struct node *k1, *k2, *prev1, *prev2;

if (!head || k < 1 || k > length)
return NULL;

prev1 = prev2 = NULL;

/*k1 is the kth node from begining and prev1 is previous to k1*/

/*k2 is the kth node from end and prev2 is previous to k2*/
k2 = find_kth_node_from_end(head, k, length, &prev2);

if (k1 == NULL || k2 == NULL)
return NULL; /*the k value is incorrect*/

if (k1 == k2)
return head; /*both nodes are the same. So no need to swap*/

/*Handle the case where k1 and k2 are neighbors and return*/
if (k1->next == k2)

if (k2->next == k1)

/*k1 and k2 are not neighbors. So swap k1.next with k2.next*/
temp = k1->next;
k1->next = k2->next;
k2->next = temp;

if (prev1) {
prev1->next = k2;
} else  {
}

if (prev2) {
prev2->next = k1;
} else  {
}

}

```

## Java

```
/*Helper function which swaps two neighbors n1 and n2
prev: node previous to n1
n1: first node to be swapped
n2: second node to be swapped. n2 occurs immediately after n1
*/
/*Swap n1 and n2*/
n1.next = n2.next;
n2.next = n1;

if (prev != null) {
prev.next = n2;
} else {
}

}

/*Main function for swapping the kth node from beginning and end
k: which node in the linked list should be swapped
length: number of nodes in the linked list
Return value: head of the result linked list on success, null on error
*/
int length)  {

if (head == null || k < 1 || k > length)
return null;

/*k1 is the kth node from begining and prev1 is previous to k1*/

/*k2 is the kth node from end and prev2 is previous to k2*/

if (k1 == null || k2 == null)
return null; /*the k value is incorrect*/

if (k1 == k2)
return head; /*both nodes are the same. So no need to swap*/

/*If k1 and k2 are neighbors, then handle this case and return*/
if (k1.next == k2)

if (k2.next == k1)

/*k1 and k2 are not neighbors. So swap k1.next with k2.next*/
k1.next = k2.next;
k2.next = temp;

if (prev1 != null) {
prev1.next = k2;
} else  {
}

if (prev2 != null) {
prev2.next = k1;
} else  {
}

}

```

## Python

```#Helper function which swaps two neighbors n1 and n2
#prev: node previous to n1
#n1: first node to be swapped
#n2: second node to be swapped. n2 occurs immediately after n1
@staticmethod
#Swap n1 and n2
n1.next = n2.next
n2.next = n1

if (prev):
prev.next = n2
else:

#Main function for swapping the kth node from beginning and end
#k: which node in the linked list should be swapped
#length: number of nodes in the linked list
#Return value: head of the result linked list on success, None on error
@staticmethod
if (not head or k < 1 or k > length):
return None

#k1 is the kth node from begining and prev1 is previous to k1

#k2 is the kth node from end and prev2 is previous to k2

if (not k1 or not k2):
return None #the k value is incorrect

if (k1 == k2):
return head #both nodes are the same. So no need to swap

#If k1 and k2 are neighbors, then handle this case and return
if (k1.next == k2):

if (k2.next == k1):

#k1 and k2 are not neighbors. So swap k1.next with k2.next
temp = k1.next
k1.next = k2.next
k2.next = temp

if (prev1):
prev1.next = k2
else:

if (prev2):
prev2.next = k1
else: