Problem

Submissions

Hints & solutions

Discuss

Delete Kth Node From End

Moderate

0/80

Average time to solve is 15m

165 upvotes

Asked in companies

Problem statement

You have been given a singly Linked List of 'N' nodes with integer data and an integer 'K'.

Your task is to remove the 'K'th node from the end of the given Linked List and return the head of the modified linked list.

Example:

Input : 1 -> 2 -> 3 -> 4 -> 'NULL'  and  'K' = 2
Output: 1 -> 2 -> 4 -> 'NULL'
Explanation:
After removing the second node from the end, the linked list become 1 -> 2 -> 4 -> 'NULL'.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains an integer 'N', the size of the linked list and an integer 'K'. 
The second line contains 'N' space-separated integers.

Output format :

The output contains the linked list after deletion. If the list is empty, -1 is printed.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you solve this without finding the length of the linked list and using O(1) extra space?

Sample Input 1 :

6 3
1 2 3 4 5 6

Sample Output 1 :

1 2 3 5 6

Explanation for Sample Input 1:

In the given linked list the node with data ‘4’ will be removed as this is the 3rd node from the end of the Linked List.

Sample Input 2 :

3 3
1 2 3

Sample Output 2 :

2 3

Constraints :

1 <= 'N' <= 10^3
1 <= 'K' <= 'N'
1 <= 'data' <= 10^3

Time Limit: 1 sec.

Hint 1

Hint 2

Hint 3

Think of storing the linked list node in the data structure

Approaches (3)

Approach 1

Approach 2

Approach 3

Using Lists

The naive solution is to process all the nodes from the front side of the linked list and keep adding a node to the list. Now we can easily remove the Kth node from the end of the list by simply replacing the next pointer of the ('LENGTH' - 'K' - 1)th node (0-based indexing from start) of the list with the ('LENGTH' - 'K' + 1)th node. This way we can remove the Kth node from the end of the linked list.

Time Complexity

O(N), where N is the number of nodes in the linked list.

In the worst-case, we will be iterating the whole linked list. Hence, the overall complexity will be O(N).

Space Complexity

O(N), where N is the number of nodes in a linked list.

In the worst case, we will be storing all nodes of the linked list in a new list.

(75% EXP penalty)

(100% EXP penalty)

Delete Kth Node From End

Console