Get Node Value

Problem Statement

You’re given the pointer to the head node of a linked list and a specific position. Counting backwards from the tail node of the linked list, get the value of the node at the given position. A position of 0 corresponds to the tail, 1 corresponds to the node before the tail and so on.

Input Format You have to complete the int GetNode(Node* head, int positionFromTail) method which takes two arguments - the head of the linked list and the position of the node from the tail. positionFromTail will be at least 0 and less than the number of nodes in the list. You should NOT read any input from stdin/console.

Output Format Find the node at the given position counting backwards from the tail. Then return the data contained in this node. Do NOT print anything to stdout/console.

Sample Input 1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 0 1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 2

Sample Output 6 3

Merge two sorted linked lists

Problem Statement

You’re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format You have to complete the Node* MergeLists(Node* headA, Node* headB) method which takes two arguments - the heads of the two sorted linked lists to merge. You should NOT read any input from stdin/console.

Output Format Change the next pointer of individual nodes so that nodes from both lists are merged into a single list. Then return the head of this merged list. Do NOT print anything to stdout/console.

Sample Input 1 -> 3 -> 5 -> 6 -> NULL 2 -> 4 -> 7 -> NULL

15 -> NULL 12 -> NULL

NULL 1 -> 2 -> NULL

Sample Output 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 12 -> 15 -> NULL 1 -> 2 -> NULL

Explanation 1. We merge elements in both list in sorted order and output.

Compare two linked lists

Problem Statement

You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. The lists are equal only if they have the same number of nodes and corresponding nodes contain the same data. Either head pointer given may be null meaning that the corresponding list is empty.

Input Format You have to complete the int CompareLists(Node* headA, Node* headB) method which takes two arguments - the heads of the two linked lists to compare. You should NOT read any input from stdin/console.

Output Format Compare the two linked lists and return 1 if the lists are equal. Otherwise, return 0. Do NOT print anything to stdout/console.

Sample Input

NULL, 1 --> NULL 1 --> 2 --> NULL, 1 --> 2 --> NULL

Sample Output 0 1

Explanation 1. We compare an empty list with a list containing 1. They don't match, hence return 0. 2. We have 2 similar lists. Hence return 1.

Reverse a linked list

Problem Statement

You’re given the pointer to the head node of a linked list. Change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.

Input Format You have to complete the Node* Reverse(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console.

Output Format Change the next pointers of the nodes that their order is reversed and return the head of the reversed linked list. Do NOT print anything to stdout/console.

Sample Input

NULL 2 --> 3 --> NULL

Sample Output NULL 3 --> 2 --> NULL

Explanation 1. Empty list remains empty 2. List is reversed from 2,3 to 3,2

Print in Reverse

Problem Statement

You are given the pointer to the head node of a linked list and you need to print all its elements in reverse order from tail to head, one element per line. The head pointer may be null meaning that the list is empty - in that case, do not print anything!

Input Format You have to complete the void ReversePrint(Node* head) method which takes one argument - the head of the linked list. You should NOT read any input from stdin/console.

Output Format Print the elements of the linked list in reverse order to stdout/console (using printf or cout) , one per line.

Sample Input

1 --> 2 --> NULL 2 --> 1 --> 4 --> 5 --> NULL

Sample Output 2 1 5 4 1 2

Explanation 1. First list is printed from tail to head hence 2,1 2. Similarly second list is also printed from tail to head.

Delete a Node

Problem Statement

You’re given the pointer to the head node of a linked list and the position of a node to delete. Delete the node at the given position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The list may become empty after you delete the node.

Input Format You have to complete the Node* Delete(Node* head, int position) method which takes two arguments - the head of the linked list and the position of the node to delete. You should NOT read any input from stdin/console. position will always be at least 0 and less than the number of the elements in the list.

Output Format Delete the node at the given position and return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

1 --> 2 --> 3 --> NULL, position = 0 1 --> NULL , position = 0

Sample Output 2 --> 3 --> NULL NULL

Explanation 1. 0th position is removed, 1 is deleted from the list. 2. Again 0th position is deleted and we are left with empty list.

Insert a node at a specific position in a linked list

Problem Statement

You’re given the pointer to the head node of a linked list, an integer to add to the list and the position at which the integer must be inserted. Create a new node with the given integer, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is empty.

Input Format You have to complete the Node* Insert(Node* head, int data, int position) method which takes three arguments - the head of the linked list, the integer to insert and the position at which the integer must be inserted. You should NOT read any input from stdin/console. position will always be between 0 and the number of the elements in the list (inclusive).

Output Format Insert the new node at the desired position and return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

NULL, data = 3, position = 0 3 --> NULL, data = 4, position = 0

Sample Output 3 --> NULL 4 --> 3 --> NULL

Explanation 1. we have an empty list and position 0. 3 becomes head. 2. 4 is added to position 0, hence 4 becomes head.

Note For the purpose of evaluation the list has been initialised with a node with data=2. Ignore it, this is done to avoid printing empty lists while comparing output.