DELETE Kth NODE FROM THE END

Concepts Used

Basics of linked list.

Difficulty Level

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).

Note: This algorithm needs two traversals(one to find L). The below algorithm is one pass algorithm.


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);
    struct node* head=newnode(x);
    struct   node* headlist=head;
    for(int i=1;i<n;i++)
    {
     int y;scanf("%d",&y);
     head->next=newnode(y);
     head=head->next;
    }
    struct node* prev=NULL,*current=headlist;
    for(int i=1;i<k;i++)
    {
     prev=current;
     current=current->next;
    }
    if(prev==NULL)
    {
     headlist=current->next;
    // delete(current);
    }
    else
    {
     struct node* nxt=current->next;
     prev->next=nxt;
     //delete(current);
    }
     while(headlist!=NULL)
    {
     printf("%d ",headlist->data);
      headlist=headlist->next;
    }
    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;
    node* head=newnode(x);
    node* headlist=head;
    for(int i=1;i<n;i++)
    {
     int y;cin>>y;
     head->next=newnode(y);
     head=head->next;
    }
    node* prev=NULL,*current=headlist;
    for(int i=1;i<k;i++)
    {
     prev=current;
     current=current->next;
    }
    if(prev==NULL)
    {
     headlist=current->next;
     delete(current);
    }
    else
    {
     node* nxt=current->next;
     prev->next=nxt;
     delete(current);
    }
     while(headlist!=NULL)
    {
     cout<<headlist->data<<" ";
      headlist=headlist->next;
    }
    cout<<"\n";
    }

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

    class LinkedList 
    { 
    Node head; 
    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); 
        new_node.next = head; 

        head = new_node; 
    } 
    void deleteNode(int position) 
    { 
        if (head == null) 
            return;  
        Node temp = head; 
        if (position == 0) 
        { 
            head = temp.next; 
            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() 
    { 
        Node tnode = head; 
        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();
        LinkedList llist = new LinkedList(); 
        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(); }
    } 
     } 


Previous post TOYS
Next post Find a Number

Leave a Reply

Your email address will not be published. Required fields are marked *