Linked List Insertion

Problem

Create a link list of size N according to the given input literals. Each integer input is accompanied by an indicator which can either be 0 or 1. If it is 0, insert the integer in the beginning of the link list. If it is 1, insert the integer at the end of the link list.

Hint: When inserting at the end, make sure that you handle NULL explicitly.

Examples:

Example 1:

Input:
LinkedList: 9->0->5->1->6->1->2->0->5->0
Output: 5 2 9 5 6
Explanation:
Length of Link List = N = 5
9 0 indicated that 9 should be
inserted in the beginning. Modified
Link List = 9.
5 1 indicated that 5 should be
inserted in the end. Modified Link
List = 9,5.
6 1 indicated that 6 should be
inserted in the end. Modified Link
List = 9,5,6.
2 0 indicated that 2 should be
inserted in the beginning. Modified
Link List = 2,9,5,6.
5 0 indicated that 5 should be
inserted in the beginning. Modified
Link List = 5,2,9,5,6. 
Final linked list = 5, 2, 9, 5, 6.

Example 2:

Input:
LinkedList: 5->1->6->1->9->1
Output: 5 6 9

Your task:

You only need to complete the functions insertAtBeginning() and insertAtEnd() that takes the head of link list and integer value of the data to be inserted as inputs and returns the head of the modified link list.

• Expected Time Complexity: $O(1)$ for insertAtBeginning() and $O(N)$ for insertAtEnd()
• Expected Auxiliary Space: $O(1)$ for both

Constraints:

• $1<=N<=10^4$

Solution

Python

def insertAtBegining(self,head,x):
    new_node = Node(x)
    new_node.next = head
    head = new_node
    return head
    
def insertAtEnd(self,head,x):
    new_node = Node(x)
    if head is None:
        head = new_node
    else:
        temp = head
        while temp.next is not None:
            temp = temp.next
        temp.next = new_node
    return head

Java

Node insertAtBeginning(Node head, int x) {
    Node new_node = new Node(x);
    new_node.next = head;
    head = new_node;
    return head;
}
 
Node insertAtEnd(Node head, int x) {
    Node new_node = new Node(x);
    if (head == null) {
        head = new_node;
    } 
    else {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new_node;
    }
    return head;
}

C++

Node *insertAtBegining(Node *head, int x) {
    Node *new_node = new Node(x);
    new_node->next = head;
    head = new_node;
    return head;
}
    
Node *insertAtEnd(Node *head, int x)  {
    Node *new_node = new Node(x);
    if (head == nullptr) {
        head = new_node;
    } 
    else {
        Node *temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
    return head;
}

C

struct Node *insertAtBegining(struct Node *head, int x) {
	struct Node *new_node = (struct Node*) malloc(sizeof(struct Node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return head;
    }
    new_node->data = x;
    new_node->next = head;
    head = new_node;
    return head;
}

struct Node *insertAtEnd(struct Node *head, int x)  {
    struct Node *new_node = (struct Node*) malloc(sizeof(struct Node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return head;
    }
    new_node->data = x;
    new_node->next = NULL;
    if (head == NULL) {
        head = new_node;
    } 
    else {
        struct Node *temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
    return head;
}

• Time Complexity: $O(1)$ for insertAtBeginning() and $O(N)$ for insertAtEnd()
• Auxiliary Space: $O(1)$ for both