Reverse a doubly linked list

Problem Statement

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty.

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

Output Format Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Then return the head node of the reversed list. Do NOT print anything to stdout/console.

Sample Input

NULL NULL <-- 2 <--> 4 <--> 6 --> NULL

Sample Output NULL NULL <-- 6 <--> 4 <--> 2 --> NULL

Explanation 1. Empty list, so nothing to do. 2. 2,4,6 become 6,4,2 o reversing in the given doubly linked list.

Find Merge Point of Two Lists

Problem Statement

You’re given the pointer to the head nodes of two linked lists that merge together at some node. Find the node at which this merger happens. The two head nodes will be different and neither will be NULL.

[List #1] a--->b--->c--> x--->y--->z--->NULL / [List #2] p--->q-->x-->y-->z

In the above figure, both list merges at node x.

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

Output Format Find the node at which both lists merge and return the data of that node. Do NOT print anything to stdout/console.

Delete duplicate-value nodes from a sorted linked list

Problem Statement

You're given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete as few nodes as possible so that the list does not contain any value more than once. The given head pointer may be null indicating that the list is empty.

For now do not be concerned with the memory deallocation. In common abstract data structure scenarios, deleting an element might also require deallocating the memory occupied by it. For an initial intro to the topic of dynamic memory please consult: http://www.cplusplus.com/doc/tutorial/dynamic/

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

Output Format Delete as few nodes as possible to ensure that no two nodes have the same data. Adjust the next pointers to ensure that the remaining nodes form a single sorted linked list. Then return the head of the sorted updated linked list. Do NOT print anything to stdout/console.

Sample Input 1 -> 1 -> 3 -> 3 -> 5 -> 6 -> NULL NULL

Sample Output 1 -> 3 -> 5 -> 6 -> NULL NULL

Explanation 1. 1 and 3 are repeated, and are deleted. 2. Empty list remains empty.

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