# DELETE Kth NODE FROM THE END

Easy

#### Problem Statement :

You are given a singly-linked list, delete the kth
node from the end of the list and then print Linked list after deletion of the kthnode.
> Note: Given k will be always valid.

#### EXAMPLE:

``````Given: 1->2->3->4->5->6
K=3

after deletion:
1->2->3->5->6

4 is the third last node from the end of linked list.``````

You are encouraged to try the problem on your own before looking at the solution by our online coding courses.
See original problem statement here

## EXPLANATION: ## Brute force:

Start with the first node and count the number of nodes present after that node.If the number of nodes are
If the number of nodes are > K-1 then go to the next node.

Continue this until the number of nodes after current node are K-1.

``````Time complexity: O(n*n) ,for scanningthe remaining list (from current node) for each list.
Space complexity: O(1).``````

`Can we make this any better?`

## Approach 2:

If L is the length of the linked list,(L−k+1) th node from the beginning is Kth node from the ned of the linked list.

Look at the example: K=4;

You can see that the 4th node from the end is the same node which is 2nd from the beginning (L-K+1=5-4+1).

So the problem could be simply reduced to another one : Remove the (L−k+1) th node from the beginning in the list , where L is the list length. This problem becomes easy if we find the length of the list .

``````Time Complexity: O(n).

Space complexity: O(1).``````

## Approach 3:

Use two pointers lKthNode and lTemp.Initially, both points to head node of the list.lKthNode starts moving only after lTemp made K moves.

From there both moves forward until lTemp reaches the end of the list. As a result lKthTemp points to the kth node from the end of the linked list.

``````Time Complexity: O(n).

Space complexity: O(1).``````

## SOLUTIONS:

``` #include <stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* next;
};
struct node* newnode(int x)
{
//struct node* temp=new node();
struct node* temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=x;
temp->next=NULL;
return temp;
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n,k;scanf("%d%d",&n,&k);
int x;scanf("%d",&x);
for(int i=1;i<n;i++)
{
int y;scanf("%d",&y);
}
for(int i=1;i<k;i++)
{
prev=current;
current=current->next;
}
if(prev==NULL)
{
// delete(current);
}
else
{
struct node* nxt=current->next;
prev->next=nxt;
//delete(current);
}
{
}
printf("\n");
}

return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
};
node* newnode(int x)
{
node* temp=new node();
temp->data=x;
temp->next=NULL;
return temp;
}
int main()
{
int t;cin>>t;
while(t--)
{
int n,k;cin>>n>>k;
int x;cin>>x;
for(int i=1;i<n;i++)
{
int y;cin>>y;
}
for(int i=1;i<k;i++)
{
prev=current;
current=current->next;
}
if(prev==NULL)
{
delete(current);
}
else
{
node* nxt=current->next;
prev->next=nxt;
delete(current);
}
{
}
cout<<"\n";
}

return 0;
}
```
```import java.util.*;
import java.io.*;

{
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);

}
void deleteNode(int position)
{
return;
if (position == 0)
{
return;
}
for (int i=0; temp!=null && i<position-1; i++)
temp = temp.next;
if (temp == null || temp.next == null)
return;

Node next = temp.next.next;

temp.next = next;
}
public void printList()
{
while (tnode != null)
{
System.out.print(tnode.data+" ");
tnode = tnode.next;
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
int n = sc.nextInt();
int k = sc.nextInt();
int p[]=new int[n];
for(int i=0;i<n;i++)
{
p[i] = sc.nextInt();
}
for(int i=n-1;i>=0;i--)
{
llist.push(p[i]);
}

llist.deleteNode(k-1);
llist.printList(); }
}
}
```