Delete alternate nodes
Given a Singly Linked List of integers, delete all the alternate nodes in the list.

Example:

List: 10 - 20 - 30 - 40 - 50 - 60 - null Alternate nodes will be: 20, 40, and 60. Hence after deleting, the list will be: Output: 10 - 30 - 50 - null

Note :

The head of the list will remain the same. Don't need to print or return anything.

Input format :

The first and the only line of input will contain the elements of the Singly Linked List separated by a single space and terminated by -1.

Output Format :

The only line of output will contain the updated list elements.

Input Constraints:

1

Question

Delete alternate nodes

Given a Singly Linked List of integers, delete all the alternate nodes in the list.

Example:

List: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null
Alternate nodes will be:  20, 40, and 60.

Hence after deleting, the list will be:
Output: 10 -> 30 -> 50 -> null

Note :

The head of the list will remain the same. Don't need to print or return anything.

Input format :

The first and the only line of input will contain the elements of the Singly Linked List separated by a single space and terminated by -1.

Output Format :

The only line of output will contain the updated list elements.

Input Constraints:

1 <= N <= 10 ^ 6.
Where N is the size of the Singly Linked List

Time Limit: 1 sec

Accepted Answer

1. I gave an approach in which I reversed the whole linked list and then reversed every word.
2. Time complexity was thoroughly discussed and my interviewer was happy with my code.

Accepted Answer

Two Pointer Approach

Let us maintain two pointers, curr and currNext. currNext will be used for storing the pointer of the node next to the node pointed by curr. curr is initialized with the head of the list initially. Then the algorithm follows:

While curr or curr→next is not NULL:

Assign curr→next to currNext.
Change curr→next to currNext→next.
Move curr to curr→next.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the size of the linked list.

We are traversing the linked list once that takes O(N) time. Hence, the overall Time Complexity is O(N).

Given a Singly Linked List of integers, delete all the alternate nodes in the list.

Example:

Note :

Input format :

Output Format :

Input Constraints:

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer