Insert a node into a sorted doubly linked list

Problem Statement

You’re given the pointer to the head node of a sorted doubly linked list and an integer to insert into the list. Create a node and insert it into the appropriate position in the list. The head node might be NULL to indicate that the list is empty.

Input Format You have to complete the Node* SortedInsert(Node* head, int data) method which takes two arguments - the head of the sorted, doubly linked list and the value to insert. You should NOT read any input from stdin/console.

Output Format Create a node with the given data and insert it into the given list, making sure that the new list is also sorted. Then return the head node of the updated list. Do NOT print anything to stdout/console.

Sample Input

NULL , data = 2 NULL <-- 2 <--> 4 <--> 6 --> NULL , data = 5

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

Explanation 1. We have an empty list, 2 is inserted. 2. Data 5 is inserted such as list remains sorted.

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.

Insert at head of linkedlist

Problem Statement

You’re given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer, insert this node at the head of the linked list and return the new head node. 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) method which takes two arguments - the head of the linked list and the integer to insert. You should NOT read any input from stdin/console.

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

Sample Input

NULL , data = 1 1 --> NULL , data = 2

Sample Output 1 --> NULL 2 --> 1 --> NULL

Explanation 1. We have an empty list, on inserting 1, 1 becomes new head. 2. We have a list with 1 as head, on inserting 2, 2 becomes the new head.

Insert at end of linkedlist

Problem Statement

You’re given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer, insert this node at the tail of the linked list and return the head node. 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) method which takes two arguments - the head of the linked list and the integer to insert. You should NOT read any input from stdin/console.

Output Format

Insert the new node at the tail and just return the head of the updated linked list. Do NOT print anything to stdout/console.

Sample Input

NULL, data = 2

2 --> NULL, data = 3

Sample Output

2 -->NULL

2 --> 3 --> NULL

Explanation

1. We have an empty list and we insert 2.

2. We have 2 in the tail, when 3 is inserted 3 becomes the tail.